I've been having this problem with my AppleTV 2 (720) for months now, intermittently. Had tried many things including full settings reset, restarts, unplugs and it was still really clunky after being perfect and brilliant for a long long while
My solution (which interestingly also fixed the same server errors I was getting with the YouTube app on ATV) was as follows:
in iTunes on my Macbook, went into my Account and edited my payment information. Inputed the 3 digit security code from my associated debit / credit card
Did a 6 second remote reset as decribed in the above thread
After this everything is fixed, including better iTunes Match performance when I add tracks to iTunes. Previously it was taking an age to 'send information to Apple' and then 'receive results' before tracks would appear via Match in ATV. This is now slick again
Frustrating that Apple's solution to what appears to be a common problem is ridiculous!
Sam