1. The storage of playlists needs to be more user friendly. Most other media players I've used have had a much more straight-foward way of managing and storing playlists. Look at how MusicMatch, Ultraplayer, WinAmp, and other do it.
2. Random playing needs to be more random and not the same sequence every time. Also, if you choose a different track off the playlist, don't go back to playing skipped tracks. I find this behavior very annoying.
3. Show whats playing on the start bar like MusicMatch does instead of just saying "Windows Media Player". It's very nice to have something like "track (artist)" show up in the tooltip.