Try erasing all of the data from your device and resynchronizing it. There's an option for "Erase All Content" or something to that effect on the Device tab of the Settings section.
If that works, maybe it was just because the software erroneously "thought" that the songs were already on the device despite the fact that they weren't. Therefore, it wouldn't try to add what's already there.

|