Well well well, how interesting.
I traced the problem down to ONE song that wasn't syncing correctly. When you click on "Music" on the phone when it's connected, it would show up greyed out with a dotted circle in the lefthand column.
After removing this song from my library, restarting the phone, clearing out all the music (again!) and syncing, everything seems to be working correctly.
*crosses fingers*
So if you're having problems syncing, look in the Music list on your phone (while it's connected to iTunes) for tracks that failed to sync.
The funny thing is this was a track that was downloaded from the iTunes store. But it's an old DRMed version of a track I've since acquired sans-DRM, so it doesn't matter and I deleted it. I'd expect any problems to be caused by NON-iTunes Store content!
