Apple TV & computer itunes
I'm guessing this might have to do with iTunes in the Cloud. 

iTunes has the ability to show you everything that is stored locally, or show you everything you've ever purchased from the iTunes store. 

From the VIEW menu click "Show Movies in the Cloud". This will make sure you're seeing everything you own.

Alternatively you might have your iTunes set to only show un-watched movies. Make sure that you're not in the "unwatched" view. 

The new Apple TVs have no real internal storage so if you're seeing stuff on the Apple TV it either means it's on your machine or in the cloud.