Well, you've proven that the problem lies with the iPod, and not with iTunes. There is a higher level of restore which might be in order. I can't remember what its called; DM? DMR? Something like that. You can google it and it is available in the help section of the Apple site. Pretty common; not too hard to find even if I don't have the real name of it for you. DFU mode! That's it!
You might also just mount the iPod HDD in Disk Utility and take a look at it. If anything looks fishy, just reformat the HDD. After all, the iPod really has no firmware on the user partition of the HDD, the OS is installed from iTunes. Just have the latest version downloaded and ready to go so that you can install it after you reformat. Or maybe that happens in the cloud these days (things have changed since I last updated an iPod OS). And always have a backup of the media in iTunes so you don't lose anything that might be just on the iPod.
And there's always the Genius Bar if that doesn't work.
This is one of the reasons that I prefer flash storage on the iPod; HDDs just have too many potential failure scenarios. The only iPod that makes sense anymore is the Touch, because it has lots of flash storage, plus iOs (ironically, I have 7 ipods, 6 of which still work, and not one of them is a Touch. Go figure.)