Here are a number of things to try...
Check your iPod with Diagnostics Mode
It is possible that your iPod's hard drive has started to fail. Take your iPod and place your right thumb on the centre SELECT button and your left on the top MENU button. Press down both thumbs for about 6 seconds until your iPod reboots. Immediately move your left thumb around to the rewind button |<< on the left and hold this down together with SELECT for a further 6 seconds. Your iPod should now switch into Diagnostic Boot mode. Press MENU for Manual Test, then select IO > HardDrive > HDSMARTData to reveal your stats. For comparison here are mine taken when my 6th Generation Classic was about 2 years old:
Pending Sectors: 0
PowerOn Hours: 2202
Temp: Current 24c
Temp: Min 10c
Temp: Max 50c
Take a note of your results. When finished press MENU+SELECT for 6 seconds to reset the iPod again.
With modern disc drives sectors are no longer marked bad by a disc scan, if the SMART firmware detects a sector it has trouble accessing it will attempt to invisibly reallocate it to a spare area of the disc.
Note that I've only 12 remapped sectors and none pending. To help explain what the numbers mean here is an extract from the Wikipedia S.M.A.R.T. article:
Reallocated Sectors Count
Count of reallocated sectors. When the hard drive finds a read/write/verification error, it marks this sector as "reallocated" and transfers data to a special reserved area (spare area). This process is also known as remapping, and "reallocated" sectors are called remaps. This is why, on modern hard disks, "bad blocks" cannot be found while testing the surface – all bad blocks are hidden in reallocated sectors. However, as the number of reallocated sectors increases, the read/write speed tends to decrease. The raw value normally represents a count of the number of bad sectors that have been found and remapped. Thus, the higher the attribute value, the more sectors the drive has had to reallocate.
Pending sector count
Number of "unstable" sectors (waiting to be remapped, because of read errors). If an unstable sector is subsequently written or read successfully, this value is decreased and the sector is not remapped. Read errors on a sector will not remap the sector (since it might be readable later); instead, the drive firmware remembers that the sector needs to be remapped, and remaps it the next time it's written.
Large numbers of Reallocs or Pending Sectors would suggest your drive is failing and that you may need to repair or replace your iPod. Check your stats after another attempt to update your iPod. If the numbers increase that again points to hard drive failure. While it won't be good news at least you'll know it isn't some random software problem and you can decide what to do next.
Check iPod hard-drive for errors
Assuming the diagnostics give the drive a clean bill of health it may still be worth checking the drive for logical file system errors.
Hold MENU+SELECT on the iPod for about 6 seconds until it resets, then switch to PLAY+SELECT as soon as the Apple logo appears, again for about 6 seconds to put the machine in disk mode. Open iTunes and in the Devices tab of the preferences menu check Prevent iPods, iPhones, and iPads from syncing automatically. Now connect your iPod to the computer, wait until it connects, then close iTunes.
Windows: Browse My Computer and right-click on the drive for the iPod, click Properties, then click Tools. Under Error-checking, click Check Now. Under Check disk options, select Scan for and attempt recovery of bad sectors (Optional - takes ages but a good idea if you've reason to suspect physical damage). Click Start.
Mac: Run Disk Utility / Repair Disk for the equivalent process.
This should find and correct any errors in the logical & physical structures of your iPod's hard drive. Once these have been fixed you can reset the iPod (hold MENU+SELECT) and should stand a better chance of a successful restore. It might also pay to check the status of the source drive containing your media, particularly if no errors were found on the iPod.
If the device still won't restore normally try this method. Connect the device to the USB cable, press MENU+SELECT like a standard reset but keep holding for 12 seconds. The device should reboot as normal and then the screen should go blank. Now open iTunes and try to restore again.
If all else fails try Erase your iPod - The Super Fix for most iPod Problems. Basically a low level format of the iPod’s hard drive to get around whatever problems are stopping iTunes from restoring it properly.
Break up large transfers
Once you've restored your iPod don't rush to dump all the data back exactly as it was before. I have found that lots of large or complex smart playlists can sometimes trigger constant reboots or dumping of the iPod's library. In addition, larger transfers can fail leaving data in an inconsistent state. Try this technique for populating the iPod in stages.
In iTunes select the menu item File... New Smart Playlist. Change the first drop-down box to Playlist, the next to is and the next to Music or whatever playlist holds the bulk of the content you want on your device. Tick against Limit to, type in say 10, then change the drop-down to GB, and set the last drop-down to artist. When you click OK you can enter a name for the playlist, e.g. Transfer.
Now sync this playlist to your iPod rather than your entire library. When the sync is complete modify the rule (File... Edit playlist) to increase the size by your chosen amount, then sync and repeat. You can experiment with different size increments, if it doesn't work just choose something a bit smaller until it works each time. Before long you should have all your music on your iPod. Once that's done you can move on to other media such as podcasts, videos, photos, playlists, etc.