It's that MP4 is a very wide range of specs, and some phones or devices are very 'picky' about what will or won't run.
It could be that the width/height of the original is too much for the phone, or that the sound codec is not supported.
Best way out of this, I found, is to run the 'problem' videos through a converter program, such as;
Videotovideo, where you choose your phone from a list, and the format will be adjusted to work for it.
You then have to save the modified, working version to a different folder, but if it works it's worth the effort.
With my old Nokia, it would playback .3GP format but not MP4, so I had to do the conversion every time.
With Videotovideo software it's possible to adjust many parameters, framerate, width/height, bitrate, sound bitrate etc, so you might have to do a few trial runs to find the right combination, or the default 'preset' might be right for you phone, it's a free and excellent program in my opinion.