Abra o Terminal (pressione Ctrl, Alt e "T" ao mesmo tempo), copie e cole (você precisará colar clicando com o botão direito do mouse na janela do Terminal):
sudo apt-get install fglrx fglrx-core fglrx-amdcccle fglrx-pxpress
Deixe o Terminal fazer o que precisa e repita com isso:
sudo ln -svT /usr/lib /usr/lib64 #Only for Ubuntu 64bits
E finalmente isso:
sudo amdconfig --initial
Reinicie seu computador e veja como você está ...