Sometimes after a failed restore, the iPod will show up in Disk Management as being unreadable, rather than specifying FAT or FAT32. I wanted to make sure this wasn't happening in your case. But, since the iPod is at least recognized in disk management, I'd suggest attempting to format it there. After this is done, try to restore the iPod in iTunes again.
Put the iPod into disk mode first, as indicated above.
Open My Computer and you should see the iPod listed there. Make sure the drive letter on it is the one that you had changed it to earlier (to ensure you're working with the iPod). Right-click on the iPod and click Format. Ensure "QuickFormat" is not checked. Leave the remainder of the settings on their default, and then click Format.
It is normal for this to take some time, and for the iPod to run warmer than usual while completing the format.
CG