I know of no fix for the PSP firmware but...
did you give
LightMP3 a chance?
It is a powersaving MP3 player for the PSP it supports Playlists and Shuffle, it can search your whole Memorystick for media files,
supports some file formats and can use skins.
I found no real manual how to use it but many things are intuitive
(select changes the play mode (normal, repeat all, repeat title, shuffle, shuffle repeat), start switches the Display on/off, X starts playing, O stops, left + right trigger nacigates through the menu or while playing skips to the last / next title...)