Ver 6.1 solution
What worked for me:
Settings -> iTunes & App Store -> Turn on iTunes Match
At this point it complained I wasn't in the US App Store and then switched me back to US. Never again will I try to buy a song exclusive to UK iTunes! Very strange they didn't test for this, one way doors are not cool!