The best thing to do is download 3GP_Converter, you pop a video into its small window and it automatically converts the video to the right format, decreases file size, AND makes the video fit the psp screen at full. Google it, it makes things SUPER easy.
Also, once you get the 2 files that are outputted, connect your psp, and in the drive that contains the psp stuff you will see folders PSP, and MP_ROOT, go into MP_ROOT and you should find a folder called 100MNV01, any others...dont worry about but dont stick your videos in them. Stick your videos into the 100MNV01 folder and presto. If you dont have these folders, its ok, simply make them.
3GP_converter is a very simple to use program, and its one of the best, it compresses files, makes them fit the screen perfectly and whatnot. For more information on psp stuff visit www.freewebs.com/akademikz/ It will explain everything, but more in depth. Especially 3dp converter.
3gp is a free program so you know. And it will convert almost ANY file type to the right one.
So dont waste your time trying to find converters, or max media manager...this is what I use and I can put a vid on my psp in minutes.