Eu faço a instalação um pouco diferente. Você poderia tentar isso:
# Add the installer script it its own directory. For example amddriver
cd amddriver
# Create deb packages for precise (12.04) or quantal (12.10)
sudo sh ./amd-driver-installer-13.35.1005-x86.x86_64.run --buildpkg Ubuntu/precise
# Force overwrite the older packages with the new ones
sudo dpkg --force-overwrite -i *.deb
Isso funciona para mim para remover:
sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*