I would not use Catalyst or any other Display bloatware, just the driver
It's possible if you had Catalyst that it left services running if you did not turn it off in msconfig>Startup and msconfig>Services before uninstalling. So if it is in fact erroring and not installed, follow Bob's suggestion to reinstall it for the purpose of uninstalling it correctly.
Then if any problems persist please post back the exact problem and any verbatim error messages.
Look over these steps to get a perfect Clean Reinstall - Factory OEM Windows 7
which are the same for retail.