Instalar fglrx-updates e fglrx-amdcccle-updates corrigiu um problema semelhante para mim.
Não se esqueça de remover o antigo fglrx primeiro:
sudo apt-get purge fglrx*
em seguida, instale
sudo apt-get install fglrx-updates fglrx-amdcccle-updates
e execute
sudo aticonfig --initial
e reboot .
Você deve ser capaz de executar fglrxinfo
e ver a saída que confirma a boa instalação.