I had the same issues with the stock mp3 player. I really like to have my audio player be able to make playlists and also move songs around inside a playlist.
I bought mp3 skins player from appworld and its alright. You can make playlists , but you cannot move songs around once its made. Also it costs about $3.99.
For me the solution is Winamp sideloaded. Works great for me , does everything above and more. Its not perfect , but a far-cry better than the ones in appworld.
I hope in OS3 it gets a little more visual flair.. its pretty bland to be honest. TAT should be able to fix that. I remember seeing an awesome media player demo on PB a while back. Thing is i cant find the youtube link for it. It was so cool looking