I just rearranged my existing music on my phone (after connecting it as a disk drive on my desktop computer). I also copied on a load of extra music, as I was getting pretty bored with the same old stuff. To my dismay when I started the stock music player I all sorts of duplicates. Most annoying.
Well to clear it up, here is what I did :
1. Open Settings -> Applications -> Manage Applications -> All -> Media Storage.
2. Clear the data from there.
3. Restart the phone.
4. Wait for the music app to rebuild all the albums, and so on.
The last part took about 5 minutes on my little old HTC Wildfire S. You can see it swirling away, when the list of artists or albums is being displayed. At first they show nothing, then gradually start to build up, and scroll off the screen.