I had this same issue. When I tried to sync downloads, check on available downloads, etc., from the iTunes program on my Macbook Pro, nothing was working. I couldn't even find the movies in my purchase history under my account, so I was getting really worried that something had gone wrong.
Luckily, I was finally was able to find the movies I'd purchased on Apple TV by doing the following:
1. Go to iTunes Store
2. Click on the QUICK LINK: Purchased
3. Click on the Movies tab. (Or music, or whatever purchase you're looking for.)
4. Make sure the "Not in My Library" tab is depressed, and your movies should appear there with a Cloud icon in the upper right-hand corner of each movie's cover art.
When I double-clicked on them, the downloads initiated.
I hope this helps you! Good luck! -Ashley