I had the same issue, same error message. Even when you install the AMD drivers, the drivers supplied with Windows 8 stayed active.
I had to manually change the drivers in Windows over to get Catalyst Control Center to load.
After you've installed the AMD 12.8 drivers right click your desktop, select Screen Resolution. Click Advanced Settings link. In the window, click Properties button, in next window click Driver tab. Click Update Driver button.
Click "Browse my computer for driver software", select the c:\AMD folder leaving "Include subfolders" checked, click Next button.Once the AMD - AMD drivers are loaded up instead of the Microsoft - AMD drivers you should be able to run Catalyst Control Center, and in turn change the overscan/underscan settings.
See my blog post: here
Footnote: Once you get it running, be careful of messing with it until AMD do a little fixit work. I tried to install Avivo on my Sapphire HD5770, now Catalyst Control Center no longer appears in context menus, and no amount of uninstalling or reinstalling has got it back.
Fortunately enough of CCC is working that the underscan has not returned. Let's hope version 12.9 comes out soon and fixes this properly.