Прежде, чем сохранять видео-файлы на телефон, необходимо переконвертировать их с параметрами, которые будут "понятны" телу.
Кроме 3gp, это тело "понимает" также и avi (без сжатия), и, желаемый Вами, mp4.
Параметры формата mp4 следующие:
Файлы MPEG-4
24 бит, 176 x 144, 15 кадров/с
На основе кадров
Видео MPEG-4 SP: 200 Кбит/с
44100 Гц, 16 бит, Стерео
Звук MPEG AAC: 128 Кбит/с
Лично я конвертировал с помощью Ulead VideoStudio 11. Там чисто тупо при создании видео файла в "Мастере фильмов" выбираешь: MPEG-4 > Мобильный телефон с поддержкой MPEG-4.
Также на форуме отписывались про Xmedia Recode. Версия бесплатная 2.0.5.3, русскоязычная. С ее помошью тоже все получается.
Главное, при ручном вводе параметров видео изображения, обратите внимание на размер и частоту кадров, которые должны быть (для любого формата) 176 x 144 и 15 кадров/с. Тогда фильм на экране тела будет приемлем для просмотра.