O que funcionou melhor para mim até agora é simplesmente pular para o tty1 com Ctrl + Alt + F1 e reinstalar o fglrx.
Para a versão estável nos repositórios do Ubuntu:
sudo apt-get install --reinstall fglrx fglrx-amdcccle
Ou se você instalou a versão de atualizações do AMD Catalyst:
sudo apt-get remove --purge fglrx-updates fglrx-amdcccle-updates
Se você instalou manualmente a partir de um arquivo baixado da AMD, navegue até a sua pasta de downloads e execute o arquivo de instalação novamente:
cd ~/Downloads
sh amd-driver-installer-catalyst-13-4-x86.x86_64.run --buildpkg Ubuntu/raring
Você precisará alterar "raring" para preciso, atrevido, confiável, etc. se tiver uma versão diferente do Ubuntu.