Here's the problem:
The problem was due to the default setting of the ATI drivers setting the underscan to 20%. Why they would do this, I have no idea.
The solution is (as you'd expect) to change some of the settings! But which settings? Not the ones on the thread with the problem images!
I found the answer on askubuntu, here.
Now if I ever decide to reinstall Linux on this box again I have the solution handy.