I run into this for Podcasts on my iPhone. I find that I can simply uncheck "sync podcasts", sync, and then check "sync podcasts", and then sync again.
I think simply resyncing the songs would work, but if the affected songs aren't grouped in some way so you can easily unsync/sync them, then a restore might be just as easy...