Resolvido fazendo o seguinte:
Eu reverti o arquivo grub como era originalmente (somente a opção de splash quieto), então:
update-grub
sudo apt-get install fglrx-updates
sudo aticonfig --initial
update-grub
Parece que instalar o driver ati a partir da GUI de atualização do driver do Ubuntu não é um processo tranquilo.