It's an issue with the AMD drivers. I had the same issue you are currently having when I was trying to update from Catalyst 11.x to 13.4. Even tried version 12.x as well.
I had many issues trying to update the drivers that includes error messages like "Radeon HD card not detected", "Install Failed". I had several "Successfully Installed" messages, but when checked, the drivers were not actually install. Other issues included native resolution of monitor could not be used (1920x1200), My choices were 1600x1200 and below, movies that I personally encoded could not be played, certain games would launch like GTA IV and Mass Effect 3, but others would not like Skyrim and Civilization 5.
It took about 4 hours of troubleshooting including editing the Registry file (not recommended!!!!) to get Catalyst 13.4 to install properly and everything to work properly.
Instead of doing what I did, I recommend you do a clean install of Windows. I am also leaning towards nVidia when I decide to upgrade.