Just replying to an old thread for those like me that aren't early adopters. Thanks for the pointers and information. I am running Ubuntu 11.10 and used MobileMediaConverter. I selected PSP profile - and it worked perfectly.
My Fuze+ is an 8Gig. I popped in a 32 Gig MicroSDHC card. Created a Videos folder on it (don't know if I really needed to). Used MobileMediaConverter PSP Profile and converted a bunch of Burns and Allen episodes.
(I tried doing it manually, and messed it up - but the app did just fine. It's a front-end for ffmpeg, so I'm sure other apps that front-end ffmpeg would do just as fine)