Your monitor can support 1280 x 1024 which means it is a 4:3 ratio, so 800 x 600 should have been fine. Clearly the problem is more deeply rooted. If you change the settings and then reboot into safe mode a second time, does Catalyst stay on the resolution you changed it to?
The only other thing we can try is an older version of Catalyst. Try to find 12.4 online, but of course be wary of where you download from. If at all in doubt, post any links you find here, and I will check them out (and get a virus lol