Without knowing which player you have I'm taking a wild guess here but I'm suspecting you may not have a true Mp4 player. The reason I say that is I ran into similar problems a year or so ago after buying someone an apparently great Mp4 devise. Indeed, the device was great, and virtually indistinguishable from the Samsung it replicated. However, the brute would not play video made in my rather expensive Main Concept encoder. I tried some of the familiar and usually solid free jobbies too such as Super. The pattern repeated, resisting my Sony Vegas suit and so on....
Anyway, it transpired that although the device was advertised as an Mp4 player that was just another bunch of marketing boswellox. Further research showed this to be a very common phenomenon. I solved it by downloading an MTV / AMV converter.
Here's a wiki on the problem. click here
I recognise I could be well wide of the mark with this guess, but the symptoms seem familiar.