Originally Posted by Chexmix

There might be a problem with your tags. Try getting some sort of ID3 Editor - not sure which ones are best for Windows (which I assume you're on), but Google is your friend here. Anyway, once you get an ID3 tag editor, go through and make sure your tracks are all tagged properly. It seems Android doesn't play nicely with ID3 v2.4 tags, so use an older standard. ID3 v1 has worked for me.

Retagging the music I put on my phone worked for me. Hopefully this helps you, too.