Расширение файла это далеко не показатель того что этот файл МР4, ты его можешь переименовать хоть в Divx или AVI но сути это не изменит.
Настоящее закодированное видео в MPEG-4 Part 14 (МР4) имеет кучу разновидностей: основные кодируемые видеопотоки: H.264/MPEG-4 Part 10 -14, MPEG-4 Part 2, H.262/MPEG-2 Part 2, H.261/MPEG-1 Part 2. Большинство техники по умолчанию выпускают с аппаратным декодером под универсальный формат H.264, MPEG-4 Part 10 AVC http://ru.wikipedia.org/wiki/H.264 - также все кодеки используют этот формат по умолчанию. Однако это не факт, что твой аппаратный плейер поддерживает эту разновидность формата. Поэтому определи сам формат (это потребует танцев с бубном) - воспользуйся утилитой Free Studio 2013 http://www.dvdvideosoft.com/ru/free-dvd-video-software.htm и опытным путем определи максимальную поддержку МР4 твоего видео - перекодируй свое видео в несколько разных форматов, запусти на телефоне и узнаешь в чем причина.
Там кодеков различных дофигищи, наверно вам какой-то нестандартный попался. Попробуйте переконвертировать с помощью другого кодека, ну или вообще в другой формат
Поменьше пикселей надо