Here's the technical answer for what's allowed:
----------
Video formats supported: H.264 video, up to 1.5 Mbps, 640 by 480 pixels, 30 frames per second, Low-Complexity version of the H.264 Baseline Profile with AAC-LC audio up to 160 Kbps, 48kHz, stereo audio in .m4v, .mp4, and .mov file formats; H.264 video, up to 768 Kbps, 320 by 240 pixels, 30 frames per second, Baseline Profile up to Level 1.3 with AAC-LC audio up to 160 Kbps, 48kHz, stereo audio in .m4v, .mp4, and .mov file formats; MPEG-4 video, up to 2.5 Mbps, 640 by 480 pixels, 30 frames per second, Simple Profile with AAC-LC audio up to 160 Kbps, 48kHz, stereo audio in .m4v, .mp4, and .mov file formats
----------
You don't say in your post...are you sure the Mbps is under 1.5? Is the pixel aspect corect? Do you have the right baseline profile and complexity version?
Is this confusing enough yet?
This is why, as nice as they are, I generally stay away from Toast and Handbrake and all those other great programs. I have no idea what a baseline profile is or how to change it. Do you?
I use Quicktime Pro's "export to iPod" setting because it always works. I play around with things like MPEG Streamclip and Handbrake from time to time...and sometimes I get something from them that works great. But when it doesn't work, I just use Quicktime. Because who has the time to worry about all these details?