It's been a LONG time since I dealt with this issue, and it seems I spend about a week reading through very few methods that worked, and a lot of "hey, this might work" ideas. But both through recall and taking a look back at some forums, the following are some things to check, to see if they work for you. This is for two reasons: 1. iTunes software versions have changed since I had the issue; and 2. I don't have an iPhone, but a Classic 160g, though recent generation. I also have pretty much anything that can be forced manual set up so that iTunes can do very little to my music library or my iPod without an action first by me. That probably makes mine not as subject to some auto changes, so combined with not having an iPhone I don't have a good way to scenario test what you are seeing.
My initial problem had been that my playlists on my iPod were arranged in random order, or at least an order different from my iTunes (e.g., arranged by album in iTunes, arranged by artist on the iPod). The issue then, and as I recall it was a bug specific to that software version, was with live updating. You had to go to each playlist, click on it from the left sidebar, click File-Get Info (aka Command-I), and deselect Live Updating. Which pretty much ticked off every person with embedded smart playlists using live updating, since it broke their live updating if they used that workaround. I believe that issue was subsequently fixed, as I arranged my playlists in random fashion, and had some set to live update and others not, and when I synched them, they all adjusted on my iPod to match my iTunes ordering regardless. But....something you might want to take a look at.
The other thing to check is that if a track/podcast/etc. is miscategorized, it wreaks absolute havoc with the playlist, either showing it as having no tracks in it, freezing it from updating, etc. I know this because I had a video labeled as an mp3 and every time I opened iTunes, it would kick the album down to Unknown Artist, then I would manually put the info in, then it would do the same thing all over again. Once it was labeled correctly, it stopped trying to change it. The typical default when you pull up the Get Info box for any playlist is "Media Kind"...."is not"..."Podcast." Change this to "Media Kind"...."is"....."Music." This effectively does the same thing as you sorting through a few thousand tracks to find a file that's mislabeled. Note that IS "Music" is a stricter definition (as single category) than is NOT "Podcast," which is everything (multiple categories) except podcasts. I've also seen somewhere that you should have "Playlist"..."is" set to "Music" as well, but this should really only apply to those playlists where you have Playlist as a condition, rather than or in addition to Media Kind.
So, those might help you, and apologies in advance if they don't - as I said, I know they've worked in the past and they've worked on Classics. And of course, if you're playlists are rocking movies and audiobooks and music videos and songs all in the same one, the whole restrict Media Kind and/or Playlist won't really help you.
Oh, and finally, sometimes shuffle creates problems too, though I never use shuffle, so that's something I've seen written and heard secondhand. Then again, if you have shuffle checked, you would kind of expect your tracks to be in a random order (though probably not reverse alpha).
