@ Sarmatian - that's not overheating. That's pixel corruption caused by bad AMD drivers combined with Skyrim's in-game AA.
Edit: Tried the above fix but it did not work. For now I will disable Skyrim's AA to play without that pixelation until there is a fix.
It should have worked. Did you just install the 12.3s (the real 12.3s, released March 28th; 12.2 incorrectly reports as 12.3 in the CCC but will have a much earlier install date) over your current driver set, or let Steam/the CCC install the newer drivers for you? None of these methods will work. You need to completely, and I do mean
completely, uninstall your borked drivers.
Download http://support.amd.com/us/gpudownload/windows/Pages/radeonaiw_vista64.aspx. (Note that that link is for 64-bit 7/Vista; I'm not sure what OS you're using.) If you are running any third party overclocking / fan profile programs like RivaTuner or MSI Afterburner, set them not to boot with Windows and shut them down at this point.
Then go to Control Panel -> Programs -> Uninstall a program. Wait for the list of installed programs to populate; if you have a lot of programs installed this will take a while. Find the AMD Catalyst Install Manager, select it, and hit "Change." The install manager will launch and give you several uninstallation options.
NOTE: Normally I recommend simply choosing the "express uninstall all AMD software." However, if you have an AMD-based motherboard or CPU, this will probably end terribly, since it will also try to yank chipset drivers, audio drivers, etc. etc. In that case, you should choose a custom install and remove only the software that pertains to your GPU. If you have an Intel CPU/motherboard, the express uninstall option is your best bet. If you have an AMD CPU and still choose express uninstall, I am not responsible for the resulting catastrophe that may ensue.
Let the uninstaller run its course. At the end, you will be prompted to reboot.
Do so. Once the reboot is finished, launch the 12.3 installer .exe you downloaded from AMD and install those. You will be prompted to reboot again once the installer is complete. Do so.
Once your system's rebooted again, you should have a fresh install of the un-borked 12.3 drivers. If you're using RivaTuner/MSI Afterburner/etc. you may feel free to re-launch them at this point and restore their usual settings (overclocks, fan profiles, etc.).