Normalmente, eu acho, a AMD já disponibiliza os drivers compilados para o Ubuntu no site. Mas pelos dados que você passou da sua placa de vídeo, parece que não tem essa opção e, outra, o driver é antigo. Mas creio que dá para resolver.
Desinstale tudo que você já instalou aí relativo ao driver da AMD (cuidado para não tirar o que não deve heim!!!)
Depois, instale:
sudo apt-get install dh-modaliases execstack dpkg-dev debhelper lib32gcc1
Execute o arquivo .sh do driver. Veja se a mensagem de erro permanece. Anteriormente o que aconteceu é que você não tinha o suficiente nem para compilar o driver, então por isso o comando passado pelo druidaobelix retornou que não havia nada instalado. Isso resolveu para mim.
Se funcionar, veja isso
aqui.
Creio que o próprio instalador vai recomendar uma opção para você seguir, senão, aconselho você a escolher a opção "Generate Distribution Specific Driver Package". Aí só depois você escolhe a opção relativa ao Ubuntu.
Nisso a compilação começa, e depois você
pode ver uma janela perguntando se você quer instalar o que foi compilado. Essa janela nem é do instalador da AMD, mas do próprio sistema, aí fica fácil diferenciar. Nessa janela, escolha
Não.
Pelo Terminal, navegue até a pasta do arquivo .sh. Os arquivos .deb compilados devem estar lá. Então rode:
sudo dpkg -i *.deb
Reinicie, e dê mais um comando:
sudo aticonfig --initial
Reinicie novamente e veja se resolveu.
Se alguma coisa der errado, os comandos para remover o driver já foram passados.
Agora, estou pensando aqui se esse driver não vai rodar só no Ubuntu 12.04