Eu tive problemas EXATAMENTE semelhantes. Aqui está o que eu fiz: eu purgou a instalação do FGLRX usando estes comandos:
sudo sh /usr/share/ati/fglrx-uninstall.sh
sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*
(se o primeiro não funcionar, é normal, use o segundo)
Então eu reiniciei, visitei a seção de download do driver da AMD, baixei os drivers de que eu precisava, correu os drivers .run em um terminal e os instalou. Reinicie, entre no Catalyst Control Center > Display Settings > Rasgue e marque-o para liberar sem rasgos.
Então eu fui em configurações de compiz via CompizConfig (você pode precisar instalá-lo via Centro de Software do Ubuntu) clicado em OPENGL e desmarcado Sync para VBlank e tudo correu bem.