Tente:
sudo apt-get install fglrx fglrx-amdcccle
Se isso não funcionar:
sudo apt-get purge xorg-driver-fglrx fglrx*
sudo apt-get install fglrx fglrx-amdcccle
Se isso não funcionar, então definitivamente há algo errado com o driver ou possivelmente o seu hardware (não é provável que seja).
sudo apt-get purge xorg-driver-fglrx fglrx*
sudo apt-get install --reinstall libgl1-mesa-glx libgl1-mesa-dri fglrx-modaliases
sudo dpkg-reconfigure xserver-xorg
... E (você provavelmente precisará disso no futuro e disse às configurações do sistema qual driver eu estava usando) instala o mesa-utils .
sudo apt-get install mesa-utils