I'm having the same exact issue, and I'm really bummed. Got the ATV2 as a gift for my dad and we tried to download an HD movie last night and we could never successfully watch it. I tried absolutely everything I could think of; tired wired and wireless internet connections, switched DNS back to ISP DNS Servers, reset the device, tried on different routers, etc. and still no luck. Netflix, internet radio, and all other services work fine without any issue.When running a bandwidth test from the Chicago, IL server from speedtest.net I get 22 down/4up.
I called Apple tech support today and they were absolutely useless. They told me I just "plan ahead" for when I want to use the device. What's the point of having such a device if I have to plan when I want to use it?
Grrrrr....