Eu tive o mesmo problema, no meu caso, o comando de reinstalação ajudou. Cole isso no terminal:
sudo apt-get install fglrx-updates --reinstall
Se não funcionar, desinstale o FGLRX:
sudo sh /usr/share/ati/fglrx-uninstall.sh
sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev* xorg-driver-fglrx
Em seguida, instale o driver usando o terminal:
sudo apt-get install fglrx-updates
Se isso não funcionar, desinstale tudo novamente e tente usar o script oficial, apenas siga esses comandos:
cd /tmp && wget -O amd-driver-installer-12-8-x86.x86_64.zip http://www2.ati.com/drivers/linux/amd-driver-installer-12-8-x86.x86_64.zip
unzip amd-driver-installer-12-8-x86.x86_64.zip
chmod +x amd-driver-installer-8.982-x86.x86_64.run
sudo sh amd-driver-installer-8.982-x86.x86_64.run
O Windows irá aparecer e você pode começar a instalar os drivers. Quando você terminar de digitar:
sudo aticonfig --initial -f
e reinicie.
O link é para os drivers ATI 12.8 de 64 bits, para obter uma versão mais recente, substitua-o por um link fornecido a você pelo site oficial da AMD, basta selecionar o seu harware.