Converting for Apple TV (Gen 1)

I assume you're using a preset for conversions? Have you gone into the problematic files to see if there is a difference?

I mainly use visualhub and vuze for conversions, no problems at all. I am on the new model if that makes a difference.

I also use Handbrake for converting video to run on my two Apple TVs (1st gen). Check on the Handbrake forum. It's worth getting a username & password.
https://forum.handbrake.fr/

Also, check Dynaflash's blog (he's one of the developers) as it has some presets that work well for the 1st gen ATV.
http://dynaflashtech.net/

Finally, make sure you're using either v0.95 or one of the nightly builds. The latter seem to give me better results. You can get the nightly builds here:
https://build.handbrake.fr/job/Mac/

Good luck. Handbrake has really allowed me to get the most from my Apple TV (1st gen).

It seems that is depends on the original content of the video files.

This is true in many cases since the encoder is context adaptive. Increasing the quality setting, for instance, can push the preset target video data rate beyond the limits of the TV1 player. (E.g., a setting of 17 once pushed an old 4:3 B&W file data to nearly 9 Mbps.) In addition, modifying the basic TV preset using advanced settings can force the profile level to 4.1 or so which is also beyond the stated TV1 limits. In the case of the former, it is easy to figure out what is wrong. However, the latter is more difficult to detect without the proper software to read the file internals.

When that happens just use custom and lower the bit rate. Learn that feel and you won't need VHub.