There is a converter, absolutely FREE that I found here int he forums when the Hero first came out. Sometimes, it's a simple as converting the frame rates for the video to play correctly. But trust me, I've got some seriously expensive converters that can't do what this does... I use it now for almost everything.
SUPER videos
Settings... Biggie is the Video, I use:
Scale - 384:288
Aspect - 4:3
Frame/Sec. - 25
Bitrate kbps - 480 (this one if too high will not play at all on Hero)
This is using the h.264/AVC codec, you can play with the other settings and see how it goes. Even if the input file is already an .mp4 you might want to run it through and see if it fixes it for play on the Hero.
Hope this helps.
Happy Trails!