Again, in my experience playing it back on your pc is one thing, playing it back on the N800 is quite another. My video files reside on sd cards that are pretty chokka and no issues.

I suggest you try different encoding techniques, there are quite a few of them posted in various threads. Search under 'Handbrake' for starters.