The following Instructions are how to install the latest ATI Catalyst Video driver on a fresh install of Ubuntu 12.04 Precise ONLY.
Caution: Only use these instructions if you have opted NOT to use the Official Ubuntu Binaries.
You need to install some dependencies to your system, do this by running these in Terminal:
sudo apt-get install build-essential cdbs fakeroot dh-make debhelper debconf libstdc++6 dkms libqtgui4 wget execstack libelfg0 dh-modaliases
sudo apt-get install ia32-libs
sudo apt-get install ia32-libs-multiarch
sudo apt-get install i386 lib32gcc1
sudo apt-get install libc6-i386
Installation and building of the drivers
sudo sh amd-driver-installer-*.run --buildpkg Ubuntu/precise
sudo dpkg -i *.deb
sudo aticonfig --initial
After this command, reboot your system. If all is right, the fglrx driver will be installed and working on your system.
Again, All of this information was jacked from http://askubuntu.com/a/126513