Step 1. Fix your sources.list
At the command prompt, execute 'sudo nano /etc/apt/sources.list' -- you'll need the multiverse and universe repositories enabled
in order to get the fglrx driver and the required modules and stuff.
What you want to do is look for a line that mentions multiverse and universe.
It may look something like this: deb http://us.archive.ubuntu.com/ubuntu/ feisty main restricted universe multiverse
It may not have main in the line, but it should have universe and multiverse. They may be on separate lines, enable any that you see by removing the # in front.
Once you're done enabling repositories, type Ctrl-X and answer "yes" when Nano asks you to write the file out.
Step 2. Disable the composite extension
Back at the command prompt, execute 'sudo nano /etc/X11/xorg.conf' -- you'll need to disable the composite extension that's enabled by default.
You'll have to add the following section to the bottom of your xorg.conf file:
Section "Extensions"
Option "Composite" "0"
EndSection
Once you're done with that, hit Ctrl-X again and write out the file to disk and get back to the commandline.
Step 3. Install the driver
Once back at the commandline, you'll need to execute the following commands:
sudo apt-get update
sudo apt-get install linux-restricted-modules-$(uname -r) #Okay if it is already installed
sudo apt-get install xorg-driver-fglrx
sudo depmod -a
Your system may complain about dependencies, just install them using sudo apt-get install <package name here>
Step 4. Modify xorg.conf to use the new driver
Once everything's finished in the above steps, you'll want to configure the driver.
Generally, this is done simply by issuing the following command: sudo aticonfig --initial.
If this fails, open xorg.conf (sudo nano /etc/X11/xorg.conf) and replace any occurence of ati with fglrx to enable the new driver.
Then, type 'sudo aticonfig --overlay-type=Xv' to set the overlay type.
Step 5. At this point, you should be able to start GDM and X by typing sudo gdm--this should get you into the desktop environment! Good luck!