Tienes varias opciones. Avidemux es la mejor, en formato h264 y 720x480. Va genial. Aunque hace unos dias dejó de irme, creo que alguna actualización se cargó algo y todo lo que convierto la PSP ya no me lo lee. Raro de cojones. Eso si, tienes que pillarte el avidemux 2.4. Pillalo en getdeb, si no está con apt-get. En Ubuntu Gutsy te trae un avidemux algo viejo que tiene la conversión psp rota.
Otra opción es el pspvc, aunque nunca he conseguido que me vaya con h264, pero si para mpeg4. Eso si, es muy limitado, no puedes ponerle una resolución alta, ni cambiarle bitrate, ni nada. Pero funciona siempre que lo hagas con mpeg4.
Y ahora estoy probando unos scripts (
http://teknoraver.campuslife.it/software/mp4tools/) que, francamente, a primera vista van de lujo. Tienen repositorio para apt, asi que son faciles de instalar. Para cambiarle la resolución editas el /usr/bin/mkpsp y puedes meterle el bitrate que quieras. Son muy faciles de usar también. También con h264 y 720x480 para verlo en la tele (si tienes una slim) de lujo.
Y no conozco nada mas, a no ser que quieras tirar de ffmpeg a mano, pero para eso hay mil webs que lo explican en google.