Eu resolvi o problema. Ou pelo menos eu espero ter :) Uma reinicialização bem sucedida até agora, dedos cruzados:)
Eu tinha um palpite de que o problema era com o driver de vídeo, ou seja, com o fato de que algum pacote fglrx * poderia ter sido atualizado. Então, eu segui meu próprio tutorial sobre a reinstalação de placas de vídeo ATI (no passado eu muito problema com meus drivers ATI, então eu escrevi esse post para me ajudar). Eu reverti para os drivers mesa , e agora a reinicialização parece funcionar:
$sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*
$sudo mv /etc/X11/xorg.conf /etc/X11/xorg.conf.bck
$sudo apt-get install --reinstall libgl1-mesa-glx:i386 libgl1-mesa-glx:amd64 libgl1-mesa-dri:i386 libgl1-mesa-dri:amd64 xserver-xorg-core
$sudo dpkg-reconfigure xserver-xorg
$sudo reboot
Por enquanto, vou manter os drivers e não instalarei o ATI oficial. De qualquer forma, o driver oficial do meu cartão é legado, atualizado pela última vez em janeiro de 2013 (bastante antigo, eu diria)