Você precisa remover todos os pacotes fglrx atuais do seu sistema
se algum destes erros retornar, por exemplo: arquivo não encontrado, pacote não encontrado ignore-o
Digite no terminal Ctrl-Alt-T
sudo sh /usr/share/ati/fglrx-uninstall.sh
sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*
Quando isso for feito, siga estas instruções para instalar o driver correto do site oficial da AMD
OR
Se você deseja instalar os binário oficiais do ubuntu, vá para Configurações do sistema > > Drivers adicionais e selecione o driver recomendado