Read this first:
http://news.com.com/2100-1041_3-520...=feed&subj=news
If it sounds similar to what you are experiencing, here is the work around:
1.Make sure you have all your songs on iTunes
2.Connect your iPod
3.Cancel the Update
4.Reset your iPod back to the factory settings
5.Connect it to iTunes and Update it