mi experiencia es la siguiente: uso ubuntu y tengo una psp. La psp, al igual que muchos moviles, usa mpeg4 sp o mpeg4-avc para el video y aac para el audio. Para el caso viene dando igual si hablamos de 3gp para un movil o mp4 para la psp, estamos en el mismo punto.
asi que intento convertir los videos con ffmpeg y mencoder de los repositorios de ubuntu. Pero los paquetes de ffmpeg y mencoder de ubuntu estan compilados sin soporte para lo que me hace falta. Los de medibuntu tampoco me funcionaron. Ni los de Marillat para Debian (y acepta mi consejo, no quieres instalar un paquete para Debian en Ubuntu, a no ser que no te importe bloquear un montón de paquetes por dependencias insatisfechas). Intenté compilar ffmpeg a manubrio, pero depende a su vez de cosas de las que no hay paquetes en ubuntu, alguna de las cuales ni siquiera tiene un makefile decente.
Sin embargo encontré un programa llamado pspvc con un script de instalacion que baja los paquetes desde donde le parece apropiado y compila con exito una version de ffmpeg que si me sirvio para mis propositos.
Asi que mi consejo es que lo intentes con el ffmpeg de serie. luego con el de medibuntu y por ultimo intentes compilarlo desde las fuentes. si eso no te funciona, quizas te valga el ffmpeg de pspvc