After reading everything I could find on this topic, and trying everything recommended, i called apple support. The only thing that I may have done differently from others perhaps is i had first deleted everything in my library in itunes. I have a big music collection and put all the music i want on my phone in one folder and add it to my library. The music disappeared from my library when i deleted it, but o matter how i synced it wouldn't come off the iphone.
Since I ust upgraded to ios 5.0.1 recently Apple support didnt charge me. My iphone 4 is just over a year, so otherwise i would have had to pay. Long story short, they had me restore the phone, backup first.
Music is off phone now and i start again.
I agree we have a software glitch, whether related to the upgrade or something else. Ther are too many similar stories for it not to be.