Dude, do be a favor. Check on your apple tv, under settings, about, to see what os your are running. in the states were are all on ios 4.0 . is that true with the new ones shipped? seeing if there is any improvement.
It's on version 4.0. I think there will be a new update soon, at the very least to add support for iTunes LP (Steve Jobs said it was coming soon)