OK, have dug around a bit more and got a bit further.
After resetting my Apple TV this is what I get:
Tried to download a couple of freebies - Lost in 8:15, 24 series 8 sneek peek etc. and it worked perfectly.
Tried to buy a song: The "cannot connect to the iTunes Store - Please try again later" message appears.
Tried to buy the same song again: got the "You have already purchased this song" and the prompt to check for downloads.
Went to downloads - check for downloads - my song downloaded immediately.
Did this with another song and got the same thing.
It's not perfect but at least it's better. Would prefer paid for content to download straight away.
Resetting Apple TV guide here:
http://support.apple.com/kb/HT3180