If your converting videos to use on your PSP and you have a 1.5 PSP use .pmp insted of .mp4.
MP4box is worth looking into (although it cant transcode, only convert), its command line but there are GUI tools for it like YAMB.
If you can't find a (decent) pure linux app, you could try an already suggested app through WINE, its going to be slow though.