i have had the same problem, i have found two work arounds
one is to re encode the video files either into WMA - (god i hate that codec)
i have never had problems playing WMA files - (You do need dev hook to play btw) or try re endocing the file with pMEnc v04. for PSPlayerMT.
the re endocing back int mp4 format had beend like 50 / 50 for me me some files everything has worked for me with WMA (firmware 2.6 or higher w/ devhook). Further more make sure you are using the right resolution 400x272 i think it is the right format, i forgot (i have it as a preset and yes i am too lazy to look right now)
furthermore you can try PMPMod but you need to encode into the AVC format which i don't know much about. all in all i think the only downfall of fw 1.5 is the very small amount of codecs it supports but thank god for DevHook and Emulated FW for wider codec support.