Weird iPhone Music Sorting Error
 

This is the second time this has happened. One day, I look at the music on my phone (iPhone 4S running iOS 6.1.3, though it previously happened with another version of iOS), and the phone thinks all the songs begin with different letters than they do. It does this same thing for the display by artist.

It suddenly thinks "A" should be filed under "O", and proceeds through the alphabet from there. When it runs out of letters, it puts everything else under "123".

If I add new music that has never been on the phone, it shows up under the correct letter. I tried wiping the phone completely, restoring from iCloud backup, and re-syncing all my music from scratch, and it still does this same thing. The only way to fix it is to wipe the phone and set it up as a new phone.

I suspect the internal database of songs is corrupt, and when I restore from iCloud I am restoring the corrupt database. But the idea of the only fix being to blow away everything and start from scratch is unacceptable.

Is there a way to either just wipe the internal database of songs (if that is what's causing the problem) or figure out what the problem is and correct it?

http://i.imgur.com/rEofffA.png

I don't use iTunes Match.