Update: I reset iPhone AGAIN as a new phone. Did the first auto-sync with apps, no problem. Then had it sync my one ringtone; success. Then I started syncing music one playlist at a time, starting with the small ones then getting increasingly larger. That last reset seems to have purged whatever the memory issue was.
Update to the update: the last (and largest) playlist got to within 50 songs then canceled with the same *#^$ message. The "Other" category grew from a couple of tens of MB to 1.36 GB, and now the rest of my music won't fit.
What is ridiculous is that the exact same playlists fit on my iPod Touch and my last iPhone 3, which had the same amount of memory. It's not system data, because it wasn't even present before I started trying to sync my music.
Stumped and frustrated by all this.