Those are all fine for TV1. The problem is probably elsewhere in the encoding.
Will it play in itunes? If so, use iTunes "Create Apple TV version" option, then pop open both the original and this new copy in quicktime. In the Window menu, open "show movie inspector". My first guess is that Data Rate will exceed TV specs. My second guess is that FPS will exceed TV specs (you need to play the video to see the average FPS). This will be most obvious by comparing the first to the second.