What's the bitrate and size (pixels) of the video?
If these are too high, the video decoder will choke because not enough data is being fed into it or it can't process it fast enough, even with frame-dropping.
If you pause and play again, it allows it to buffer some data up and can run for a little while, but then the buffer runs out again and it chokes.
On my friend's T|3, there are some movies that are very stuttery despite his PDA being 200MHz faster than my Zodiac 2.
We figured it was because the T|3 just can't keep up the data rate - The Zodiac 2 has two SD card slots - The Right hand side one is SDIO, but the Left is a high-speed slot; If I run the problem movies from the right slot it jerks like crap, but in the left slot it was smooth as... something really smooth.
Another thing to check is stuff like KeyFrames and Interleaving - Too few keyframes can cause problems and non-interleaved files can also cause problems on HD-based players (Makes no difference on FlashRAM-based devices).
One last Question:
Is the file *REALLY* MP4 (MPEG4) or is it actually AVC/H.264?
A lot of people, espescially podcasters (Damn them all!) label H.264/AVC as .MP4 or .M4V - TCPMP can't decode this format very well at the moment; You need a *really* fast CPU to do it, and anything over 480x320 will probably choke the decoder if it's a full-on all-the-features-enabled AVC file...
I personally try to stick to DivX, XviD or MPEG4 encided AVI, OGG and (slightly less) MKV because they work a lot better with TCPMP (And my Zod2 can decode them in hardware

)