Well, here's what I'm thinking...
Your file names are probably all based on the track number of the CD, followed by the name of the song. What I've discovered over the years is that Windows Media files don't play real nice with IDv2 tags. Sometimes Windows Media Player will read the tags fine, sometimes it won't, and sometimes it will mess them up.
What may be happening is that all your IDv2 tags are either unreadable by your Music Player or they may be IDv3 tags (which I've also discovered are not altogether compatible with Music Player, although an iPod reads 'em fine). I've come across a program for Windows called Mp3tag (free) that will allow you to re-edit the tag information on your songs. It will also help you add album art from Amazon.com, although you can also add your own art manually.
Be aware, if you have a lot of music files this will take some time. However, you can edit tags in a group method (based on album) by highlighting all of the songs from the same album. It won't edit track numbers or individual titles, but it will at least let you edit artist name, album name, and year of release.
This is by no means a perfect solution, and it's pretty time-consuming (I have about 400+ songs on my Captivate, and there are some I still haven't gotten around to editing). But the upshot of this is that Music Player will properly read the tags instead of the filename, and your songs should go back into alphabetical order.
Hope that helps.