Are the changes still being saved on iTunes? Is your iPhone being recognized on iTunes? If so, the syncing problem can be fixed by doing a hard reset on your iPhone. Yes I know its a shame to have to go back to factory settings but in order to keep your playlist up to date that is the best recommendation I can think of. Of course, I'm offering this suggestion because I'm assuming you've turned the phone off and back on right?
This suggestion worked on my friends iPhone 4 so best of luck to you!