Download a program called MediaCoder. It is developed by a few Chinese dudes, but is all in English. It as all of the demux/muxing codecs included for transmuxing pretty much media format. It even has a setup wizard when you start it and you can select device profiles (choose a device that is VGA) and it will convert any media file into the correct container and codec type (you are shooting for x.264 for video and AAC for audio).
Like someone else said, .mp4 is a container type and can be used for multiple codecs, both audio and video. What is most likely happening is that your current conver isn't properly transmuxing (converting) the video into the x.264 codec and is instead resizing a XvID or DIVX
encoded file and putting it into the .mp4 container.
As an alternate, you can use CorePlayer to play these files on your phone.