I successfully managed to do this this evening after having similar problems to you on the first attempt earlier in the day.
One thing I noticed after that attempt was that the kernel files in Synaptic Package Manager are very messy and reference different kernel versions. So the first thing I did was clean all that mess up.
However, you'll first need to clear up your current situation if you haven't already done so.
Open up a terminal and type:
sudo sh /usr/share/ati/fglrx-uninstall.sh
sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*
Reboot.
Then go into Synaptic Package Manager (sudo apt-get install synaptic
, if you don't already have it) and filter on "linux". Then sort alphabetically and look for the lines beginning with "linux". You'll see one file is marked for upgrade [!]. Upgrade that and reboot.
Once you're rebooted, go back into Synaptic and do the same filter again. Using a judicious install/uninstall try and make sure that all the relevant installed kernel files including "headers" type files all relate to the same kernel version. I took the latest ".18".
Once you've done that, close Synaptic and open the terminal and type the following:
sudo apt-get install linux-headers-$(uname -r)
Reboot again just for good measure and once you're back in, open up a terminal and type the following:
uname -r
You should now have the latest (.18) version of the kernel.
Open up a terminal and type:
sudo apt-get install build-essential cdbs dh-make dkms execstack dh-modaliases
sudo apt-get install ia32-libs lib32gcc1
This should take a fair while.
cd /usr ; sudo ln -svT lib /usr/lib64
Reboot again for good measure.
Now, go into Ubuntu software center, click Edit on the taskbar and select Software Sources. Select the middle option on the additional drivers tab and click on "apply changes".
Once that's done, reboot and then type the following into a terminal:
sudo aticonfig --initial -f
Then reboot once more.
Now all you need to do is type "amd" in dash to start Catalyst and set up the driver as you want it.
I recognise that some of the reboots may be unnecessary but this is exactly what I did and now I have a nice new Ubuntu 12.10 installation.
CTRL + ALT + F1
and do changes there.