About a month ago, I noticed that my iPhone had a similar problem to what the original poster has. I finally got around to researching the trouble, and have tried most of the suggestions provided in this discussion, but nothing seemed to work.
I stumbled across something yesterday that to my surprise seems to have fixed the problem, but I don't yet know if it is only a temporary fix or not. Only time will tell.
Let me give you a little background on the matter. I live in Japan (this will be important to the story later). After fooling around with so many settings in both iTunes and on my iPhone, I became really, really frustrated by this silly matter. Keeping things in alphabetical order shouldn't be this difficult.
As I said, I live in Japan. My iPhone is setup to use the English language for the operating system. My wife's phone is set to the Japanese language. I thought I would check her music organization to see if she was having any trouble with her ordering. Nothing seemed wrong with her playlists and artist/song title ordering on her iPhone, however being in the Japanese language it wasn't set to organize from A-Z. The Japanese have a different organization based on the Japanese Kana system. They have their own Kana ordering and her music was correctly ordered. (The Japanese titles were listed first in their correct order, followed by the English titles also listed in their correct order).
On a whim, I decided change my iOS over to Japanese just to see what would happen. Since I didn't have any Japanese titles on my phone, instead of listing the Japanese Kana titles first, it listed the English titles first, and lo and behold most of the titles/artists were listed under their appropriate heading. This got me excited.
I then reverted the language back to English, and again the most of the artists/song titles were still showing up under their appropriate field. I say most, because it wasn't correct for all of them. There were a few that were still misplaced, but the fix was enough to make me happy. I put the phone down and forgot about it until about 6 hours later. I wanted to check it one more time to see if the changes had stuck, and even better all of the artists and songs were now properly categorized. It's only a guess on my part, but perhaps the library needed more time to update all of the tracks and put them in their correct order. I really don't know for sure.
As of today (more than 24 hours later) everything is still in its proper place. I have yet to add any new music to the phone, as I am a bit afraid (read as chicken) to mess it all up again.
PLEASE NOTE: if you do follow this pattern, before you actually change the language be sure you take note of all the menu's and step's needed in order to change the iOS language. Once you change over to the Japanese language, it may be hard to find your way back into the language screen.
I also don't know if this is strictly associated with the Japanese language, or if it will also work with other languages as well. If you try it out, please let us know your results.