Installing ATI drivers is a tricky one often. First you want to make sure your card is truly supported by the driver you're downloading (ATI's site will tell this; don't assume anything). Second, I found the drivers from Ubuntu reposities worked better for me than if I downloaded them directly from ATI's site. Might be different for you, though.
A few things to remember: if you're using apt to handle your packages, use it to remove them too (or purge); if you remove files manually, apt might go crazy. It may even go crazy if there is a simple one-letter error in some of the scripts for a package. You definitely don't want it to go nuts, since getting apt all right again is a pain. So, if you want to use apt to install the drivers, don't mess up with the ATI's "official" ones -- or if you plan to do vice versa, don't you even try to use apt-get. And whenever installing or updating ATI's drivers you probably want to remove them first, that's what I've learned -- if some driver version is installed, it will create a problem if it just somehow can
So, now that it seems you have successfully messed up the fglrx driver install, here's what you should try:
1) remove the installed deb packages of fglrx -- if you manually removed the files, which you shouldn't be doing since you're using a package manager to handle that, try first to force a reinstall of the fglrx pacakge, and then remove it. If this doesn't work, go google, you need to do some manual work to get it done; it depends a bit on the package.
2) after you have cleaned the system, install your kernel sources -- the version
must be exactly the same as your runnin kernel's. Use apt-get for this if you have a stock kernel (i.e. you haven't compiled it yourself).
3) Choose which driver to install - from Ubuntu or from ATI (you checked out ATI's driver version supports your card, didn't you?). Then do either of them, but do not try both at the same time
If apt-get refuses to install the driver or there comes an error, find out why it did so and fix the error rather than devastating everything and trying "some other way" - that's not going to get you anywhere. If you plan to use drivers from ATI's site, then read their installation instrutions c-a-r-e-f-u-l-l-y. Read them. I know it's dull, but you will want to read them if you wish to succeed.
After the driver installation you also need to edit your X's configuration file in order to get the drivers loaded. Installing drivers like this is not a matter of double-clicking something as it seems to be in Windows, you're actually installing a new kernel module and it needs to be done correctly - there is good documentation about how this is done, so read it (INSTALL, README files or other instructions that should come with the driver package).
