Consegui fazer isso com sucesso esta noite, depois de ter problemas semelhantes a você na primeira tentativa no início do dia.
Uma coisa que notei após essa tentativa foi que os arquivos do kernel no Gerenciador de Pacotes Synaptic são muito confusos e fazem referência a versões de kernel diferentes. Então, a primeira coisa que fiz foi limpar toda essa bagunça.
No entanto, primeiro você precisa esclarecer sua situação atual, caso ainda não tenha feito isso.
Abra um terminal e digite:
sudo sh /usr/share/ati/fglrx-uninstall.sh
sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*
Reinicie.
Em seguida, vá para o Gerenciador de Pacotes Synaptic ( sudo apt-get install synaptic
, se você ainda não tiver) e filtre em "linux". Em seguida, ordene por ordem alfabética e procure as linhas que começam com "linux". Você verá que um arquivo está marcado para atualização [!]. Atualize e reinicie.
Assim que você for reiniciado, volte ao Synaptic e faça o mesmo filtro novamente. Usando uma instalação / desinstalação criteriosa, tente e certifique-se de que todos os arquivos do kernel instalados, incluindo os arquivos do tipo "headers", estejam relacionados à mesma versão do kernel. Eu peguei o último ".18".
Uma vez feito isso, feche o Synaptic, abra o terminal e digite o seguinte:
sudo apt-get install linux-headers-$(uname -r)
Reinicialize novamente apenas por precaução e, quando voltar, abra um terminal e digite o seguinte:
uname -r
Agora você deve ter a versão mais recente (.18) do kernel.
Abra um terminal e digite:
sudo apt-get install build-essential cdbs dh-make dkms execstack dh-modaliases
sudo apt-get install ia32-libs lib32gcc1
Isso deve levar um bom tempo.
cd /usr ; sudo ln -svT lib /usr/lib64
Reinicie novamente para uma boa medida.
Agora, vá para o centro de software do Ubuntu, clique em Editar na barra de tarefas e selecione Fontes de Software. Selecione a opção do meio na guia de drivers adicionais e clique em "aplicar alterações".
Depois disso, reinicialize e digite o seguinte em um terminal:
sudo aticonfig --initial -f
Em seguida, reinicie mais uma vez.
Agora tudo o que você precisa fazer é digitar "amd" no traço para iniciar o Catalyst e configurar o driver como quiser.
Eu reconheço que algumas das reinicializações podem ser desnecessárias, mas isso é exatamente o que eu fiz e agora eu tenho uma nova instalação do Ubuntu 12.10.