Odd, I had a reply, guess I ever actually hit submit.

Anyhow, Quicktime Pro should have a preset for Apple TV. Also, Handbrake is decent ( http://handbrake.m0k.org/ ), has presets and should work.

I'm guessing the reason why your initial attempt failed might have been either you had an H.264 profile selected that the Apple TV can't deal with *or too high of a bitrate. The lower end CPU in it has limits, much like any non PC device. I've had to research it a bit for encoding files to H.264 in an .mp4 container for the PS3 to play.