I had this problem with comcast internet. I believe their "speed boost" traffic shaping tricked the Apple TV into thinking I had something like a 22 megabit pipe - so the movies started playing instantly. When the boost expired, the data rate was much reduced and eventually the movie played past the delivery of the content which means my overall download wasn't fast enough to get the whole movie to my set before the movie ended.
When I changed internet providers the issues have been resolved for me. I stumbled on this by realizing I never got this error when taking my Apple TV to a friend's house with "slower" internet. The confusing part was most of the time - comcast was fast enough - but when it wasn't I still got a great initial "boost" but couldn't really watch the rental due to poor bandwidth.