I would suggest using driversweeper, especially when going from Nvidia to ATI.
Go to your control panel and use the add/remove programs tool to uninstall all of the Nvidia drivers. download driversweeper ( http://www.guru3d.com/category/driversweeper/ ) and install it. Reboot into safemode on your PC, and then run driversweeper while in safe mode- this will make sure there are no remnants of the Nvidia drivers left on your computer. Reboot your PC and then install the Catalyst Control Center and ATI drivers. This should get you set and running.
Edit: Did you reboot after uninstalling? I would make sure you uninstall both the ATI AND Nvidia drivers at this point and run Driversweeper, and make sure you are starting from somewhat of a clean start, THEN install CCC. Hopefully it will go smoother.