Existe um wiki da comunidade realmente bom sobre isso, que deve ajudá-lo neste site aqui
Pergunte Wiki da comunidade do Ubuntu ATI
O Ubuntu também tem um guia fácil de seguir aqui
Para começar, você terá que limpar a instalação que você tem de todas as informações da ATI, fazendo o seguinte comando:
sudo apt-get remove --purge fglrx-updates fglrx-amdcccle-updates
Isso limpará qualquer crudd restante / obsoleto e você poderá seguir qualquer um dos guias acima.