Esse tutorial foi tirado originalmente no ContribDoc do Caixa Mágica
1. No site da ATI, procurar a placa gráfica pretendida na secção Linux e obter um ficheiro com extensão .run:
http://ati.amd.com/support/driver.html
2. Instalar o pacote kernel-source de acordo com o kernel instalado no sistema utilizando o gestor de pacotes Synaptic ou descarregando o pacote e executando o comando [...]

De facto, têm havido muitos guias e tutorias na internet sobre como instalar as drivers da ATI no Ubuntu e nenhum deles funciona…
Aqui esse tutorial que descobri funciona perfeitamente, isso acabou com os meus problemas no Ubuntu (OpenGL)
Site de onde descobri (caso vos interesse)
Esse tutorial é válido para ambas as arquitecturas 32-bit e 64-bit:
1 – [...]