Last night we tried to rent an iTunes movie on our newish Apple TV. Instead of starting right away, the Apple TV said it would be 2+ hours before we could start watching. I’ve got a healthy 15-20Mb/s connection and a clean wire to the Apple TV, so this shouldn’t be happening.
A little bit of research turned up a surprising fix: Don’t use Google DNS.
I had the same thing happen last week. Horrendously slow downloads on my Apple TV, despite a fine network connection. Switching from Google DNS to my default DNS servers (Comcast) fixed it.