The Catalyst Team has made a software specifically designed to completely uninstall any AMD Catalyst software and drivers in your computer. You do not need to uninstall anything prior to this operation, it is a one-click tool.
(Warning: This tool removes "everything" AMD Catalyst related. From registry keys to left over files)
The link below brings you to AMD's download website. Use this software every time you update your Catalyst drivers and software!
I just wanted to bring this tutorial up because most people seem to get their hands dirty and remove the left over files and registries themselves. I for one found this by accident by browsing AMD's forum, I just thought it might be easier to find for people with issues relating to mine.