I found the default Android media player to be rather weak. The clip-art inspired UI I could overlook, however, its inability to catalog music files makes it all but useless. I loaded over 2GB of songs and a whopping four were accessible in the media player! A Google search revealed I'm not the only person with this problem. In my case, it doesn't appear that Android knows what to do with music filenames with dashes or underlines. People also report that it can't handle v2 id tags.

I've now switched to an app called museek. It has an option to organize and navigate your music collection visually. I haven't decided if this is useful or gimmicky yet. It's free and can be downloaded directly from their site. It doesn't run full-screen natively and I haven't had time to try converting it. There's an error box that pops up right after boot but after that it works fine.