Supondo que a solução seja eliminar e reinstalar conforme sugerido:
Geralmente, o comando para limpar um programa foo é sudo apt-get purge foo ou sudo apt-get remove --purge foo . Portanto, para este caso (o pacote em questão é gnome-mahjongg ) você precisa de sudo apt-get purge gnome-mahjongg , que também desinstalará o pacote mahjongg (esses são dois pacotes separados, mas mahjongg depende de gnome-mahjongg .
Como alternativa, no Synaptic, você pode escolher a opção "Marcar para remoção completa", isso é sinônimo de purge .
Em seguida, você pode simplesmente reinstalar como de costume (por exemplo, sudo apt-get install mahjongg ou simplesmente instalar via Synaptic)
Se isto ainda não funcionar, uma alternativa seria o jogo do KDE Mahjongg, kmahjongg , que pode ser instalado simplesmente digitando sudo apt-get install kmahjongg .