Depois de alguns dias, acho que encontrei a fonte do problema: certos pacotes que tornam o sistema instável. Encontre-os e remova-os. No meu caso, eu desinstalei grive
e grive-tools
, com o último não sendo projetado para o Ubuntu 12.04. Por isso, mesmo que o site deles dissesse que não encontraram problemas com o 12.04, eu o tive no meu.
Lição (da maneira mais difícil): Se você precisa manter um sistema de produção que não deve quebrar, tente ficar próximo a repositórios bem testados em vez de downloads individuais de um ou dois pacotes de compilações que não foram projetadas para o seu sistema .
Consegui reinstalar o WINE depois de remover programas que atrapalhavam o sistema. Se você tiver esse problema, procure por aqueles (especialmente aqueles que você instalou recentemente) e remova-os.