Please have a look at the ATI link in my signature. I will confess that there is some stuff there I probably need to update. But read through it. You will probably have the best luck installing from the repo using the terminal.
Here's the short version.
sudo apt-get install fglrx fglrx-amdcccle
sudo amdconfig --initial
Sometimes the driver does not install properly using the graphical tools. Also, the "Updates" version usually does not work, so I usually recommend against even bothering to try. Installing via the terminal seems to work more often.
Supposedly the amdconfig step is no longer needed, but with the number of people who end up having problems, I still recommend doing it. That is what sets up your initial "instructions" for the driver.
After you reboot, you need to open the Catalyst Control Center in administrative mode and make your fine adjustments. If it doesn't open from the menu, go back to the terminal
If all goes south, get to a terminal and do
then reboot to get back to the default Radeon driver (the one Ubuntu uses when you first install). If need be, we'll try to figure it out again from there.
sudo apt-get purge fglrx fglrx-amdcccle
Driver support for Linux has come a long way from the 90's. But it's still not always the easiest thing. Look at it from the OEM's point of view: You have one OS that 95% of your customers use. Are you going to spend your time addressing them, or the 2% of the market that uses Linux?
After all that, there's no guarantee that Steam, or your particular game, will work. Remember that Steam for Linux is still in its infancy.