Just my two cents, but I don't think the issue is with Apple's services. There seems to be quirks with the Apple TV itself. I never had issues with my Apple TV. Movies streamed well, until today. I haven't used it in a while, so not sure if it was the iOS software update I just did or recent switching of my modem by AT&T. Tried several things and was ready to give up, download times for HD said 34 hours. Then I went into the menu and chose the Reset option to set back to factory defaults. I reconnected to my wireless network and re-entered my apple id. Went to my rental and it started almost right away.
I don't have issue with movie starting. It does so ASAP. My problem is on 3 occasions, the third one tonight, the ATV gets flipped off the movie and once that happens you are screwed. I personally cannot get it to play again. It says "you have already purchased, go to a Settings, iTunes Store and then Check for a Rentals". It grinds for hours and inget fed up and go to friggin bed. This is awful. From no on I rent with my cable company because if you somehow stop the movie, at least they are smart enough to gave play button where the rent me button used to be. Give me Roku.
It is funny, using the Netflix or the YouTube app on the ATV works fine but it does not as well with rental or purchased movies from iTunes. Sometimes, I have to download a movie directly on my iPad and then airplay it to the ATV.
It is a shame that we have to wait about an hour to watch a movie. I have a nice connection and I hope the next firmware update allows you to play instantly without "save on buffer before play".