É assim que eu faço. Funciona perfekt
# eg Upgrade from AMD Catalyst 13.2 beta 2 to 13.2 beta 3
# Go into your Downloads folder (I suppose you have already download the driver)
cd Downloads
# Make the package executable
chmod +x amd-driver-installer-catalyst-13.2-beta3-linux-x86.x86_64.run
# Create deb packages for precise (12.04) or quantal (12.10)
sudo sh ./amd-driver-installer-catalyst-13.2-beta3-linux-x86.x86_64 --buildpkg Ubuntu/precise
# Force overwrite the older packages with the new ones
sudo dpkg --force-overwrite -i *.deb
# Reboot you PC
If want to unistall them
sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*