I’ve updated to a newer Xubuntu Linux on my laptop, and have installed the real ffmpeg for video encoding, since Ubuntu’s fork has an annoying tendency to crash during encodes.  That means I had to play around with command-line options to get video files compatible with the PSP.  Here’s a command line that seems to work well for ffmpeg 2.5 (current as of right now):

ffmpeg -y -i INPUTFILE -flags +bitexact -vcodec libx264 -profile:v baseline -level 3.0 -s 480x272 -r 29.97 -b:v 384k -acodec aac -b:a 96k -ar 48000 -f psp -strict -2 OUTPUTFILE.MP4

This will convert INPUTFILE to OUTPUTFILE.MP4 for playback on the PSP, with medium video quality.  if you want a better picture, increase the number after -b:v.  For better audio, increase the number after -b:a.  You can alter the resolution if you like by changing what comes after -s.  As is, the video is encoded at the native resolution of the PSP.

If you’d like a thumbnail to go along with that video, then use this:

ffmpeg -i INPUTFILE -f image2 -ss 5 -vframes 1 -s 160x120 OUTPUTFILE.THM

Enjoy!  The resulting video files will play on more than just the PSP.  They should also work on the PS3, Vita, modern phones, etc.