I've run into this too.
I Handbreak DVD to m4v. For some reason selecting Apple Universal or iPhone/iPod Touch gave me the same result. Also, selecting the iPod 5G support didn't seem to set the special bits right.
Anyways, it doesn't matter.
Also, my video (either with 1500 kbps or 100% constant) look a little liney on fast moving segments. Using H.264 with L&G Leopard, iTunes, HB and 3GS.
Once you get you video file into ITunes...do Advanced->Create iPod or iPhone Version and it will definitely play correctly on your iP device.
This is a bit of a pain, but it worked for me.
I myself haven't figured out the "magic" combo of options, etc. in Handbrake to get my DVD's to my iPhone without the extra step.
HTH,
maw