Atualizando: tentei uma solução que vi em um fórum que passava por editar o arquivo etc/network/interfaces, e bomba - o Ubuntu iniciava, mas após login no GDM, travava totalmente.
Nas tentativas de consertar esse travamento, entrei no modo de recovery, e mandei ele tentar corrigir o Xorg. Isso não resolveu o travamento, tive que entrar na linha de comando, instalar um editor de texto para o Terminal chamado "Nano" (descobri que é muito útil para casos como esse), e naveguei até achar o arquivo etc/network/interfaces novamente, e corrigir o que eu tinha mudado.
Aí destravou, só que quando eu voltei, algumas coisas estavam desconfiguradas, como por exemplo, o driver proprietário da Nvidia e o Compiz não estavam mais carregando automaticamente. Habilitei novamente essas funções, e tudo voltou ao normal.
Quando eu fui desligar o Ubuntu, qual foi minha surpresa? O problema das "letras no shutdown" tinham sumido, e agora a barrinha de avanço do encerramento estava novamente aparecendo, lindamente como acontecia no Gutsy.
Como eu resolvi isso? Sinceramente não sei, mas acredito que tenha resolvido acidentalmente, quando no travamento eu mandei ele tentar corrigir o Xorg. Ou seja, devia ser algum erro/bug/menção errada no Xorg a algum pacote inexistente, ou algo assim, que estava causando esse problema.
Não sou entendido suficientemente em Ubuntu para recomendar que outras pessoas tentem esse mesmo artifício, pois sei que o Xorg é um arquivo de configuração muito importante, e que qualquer mudança errada nele pode ser fatal. Quem quiser tentar, faça por sua conta e risco.
Abraços,
Davi.