I used to have an ATI card and had to jump many hoops getting it to work. When it did work, it ran fine, but sometimes a kernel update would make me jump all the hoops again.
When uninstalling, you may have to use the option "purge" rather than "uninstall" so that settings are deleted also.
Also, you may need to find the last working driver and not use anything above that. Mine was ./amd-driver-installer-catalyst-13.1-legacy-linux-x86.x86_64.run and nothing else worked. I think my card was a 6200. And when installing the driver i had to be in single user mode init 3 or something (i.e. not just sudo while in a gui)
When grepping my history, i see a lot of this stuff:... (read it, DO NOT RUN anything without know what you are doing)! i.e. DO NOT TAKE THIS VERBATIM, this is just some of my bash history matches in no particular order.
./bash_hist.txt: aptitude search fglrx
./bash_hist.txt: sudo aptitude install fglrx-modules-dkms
./bash_hist.txt: sudo aptitude install fglrx-driver fglrx-atieventsd fglrx-modules-dkms libfglrx libgl1-fglrx-glx xserver-xorg-video-fglrx
./bash_hist.txt: sudo aptitude purge fglrx-driver fglrx-atieventsd fglrx-modules-dkms libfglrx libgl1-fglrx-glx xserver-xorg-video-fglrx
./bash_hist.txt: sudo sh /usr/share/ati/fglrx-uninstall.sh
./bash_hist.txt: sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev*
./bash_hist.txt: sudo aptitude purge fglrx-driver
./bash_hist.txt: sudo echo -e 'Section "Device"\n\tIdentifier "My GPU"\n\tDriver "fglrx"\nEndSection' > /etc/X11/xorg.conf.d/20-fglrx.conf
./bash_hist.txt: sudo lsmod fglrx
./bash_hist.txt: sudo modprobe fglrx
./bash_hist.txt: sudo aptitude search fglrx
./bash_hist.txt: sudo aptitude reinstall fglrx-legacy-driver fglrx-legacy-modules-dkms fglrx-legacy-source libgl1-fglrx-legacy-glx
./bash_hist.txt: sudo aptitude search mesa
./bash_hist.txt: sudo apt-get install --reinstall libgl1-mesa-dri libgl1-mesa-glx xserver-xorg-core
the best thing i did was avoid ati, but you don't have that luxury on a laptop; also, that's my choice -- there are tons of people that prefer ati.
i really hope none of this makes it worse for you! when i did all this, i had to take info from many different googled resources and merge the ideas to get something working including editing xorg.conf and being certain to have a copy once something worked.