Это действительно зависит от самой платформы больше, чем фреймворк Android. Какую конфигурацию телефона / процессора / системы вы используете.
Также mp4 является только контейнером. Если внутри действительно видео MPEG4-AVC, то существует много разных профилей, битрейтов, которые могут повлиять на то, сможет ли ваш Android правильно декодировать.