One thing to try is to change the extension from .mp4 to .mov. For some reason this allows the content to be played on the Apple TV.
I've been doing this for the past few months and all have worked fine. However, in the past week or so, I've noticed that all downloads will now not even play in iTunes - whether it has an .mp4 extension or .mov extension. All play in quicktime perfectly.