So, I had amazing slow-downs, crazy tearing and yet the specs of my system should have been able to handle Skyrim on High with no problems.

The solution? My bloody ATI Control Centre was overriding the in-game settings which was obviously not taken kindly by the game.

To hopefully fix your framerate problems with ATI cards:
-go into the Catalyst Control App
-Click on the heading 'Gaming Performance' under the 'Gaming' tab
-Click the 'Standard 3D Settings' heading
-Tick the 'Custom Settings' box
-Repeat for all the headings under the 'Gaming' tab (So Anti-Aliasing and Anisotropic Filtering) by ticking 'Use Application Settings'

This solved my problems, so hopefully it helps some of you out as well.