I recently had this problem and my hard drive was fine mechanically. THIS IS WHAT FIXED IT FOR ME:
I connected my iPod but did NOT open iTunes. I clicked on my iPod as though it was a USB drive and attempted to format it. I then discovered my PC will only format the iPod in NTFS and the iPod needed to be formatted as a FAT32 format.
I found a program here: http://www.ridgecrop.demon.co.uk/index.htm that allowed me to format the iPod as a FAT32. It literally took 5 seconds when I ran the program. Finally I reconnected my iPod to iTunes and was able to restore everything as though it was a new iPod.
Here's also a link to the other forum where I discovered this: https://discussions.apple.com/thread/3564068