Try removing and Plug-ins you have installed with iTunes. See here for more information.
Otherwise, try to reformat the iPod's Hard Disk using the instructions in this article.
More often that not, this particular error message can be a good indication that your iPod's HD is going bad or faulty.
If possible, try another USB cable and port as well as restoring it again on another PC.