Ok so I had the same problem as you have (I have a fairly old 30GB ipod video). I managed to fix mine by doing the following (not sure if this was a fluke but try it and see)
1. Plug the ipod into the computer, and click restore
2. Follow all the steps of the restore, until the ipod resets (this is when the apple appears on the screen with a bar at the bottom)
3. Whilst the ipod is trying to reset, hold down Menu + Center button until it resets.
4. Afterwards, put the ipod into disk mode (holding down menu + center and then holding play + center when the apple appears) and restore it again (you may need to reset the ipod before doing this)
My iTunes had also told me that my ipod was corrupted a couple of times. Hope this helps everyone.
1. Plug the ipod into the computer, and click restore
2. Follow all the steps of the restore, until the ipod resets (this is when the apple appears on the screen with a bar at the bottom)
3. Whilst the ipod is trying to reset, hold down Menu + Center button until it resets.
4. Afterwards, put the ipod into disk mode (holding down menu + center and then holding play + center when the apple appears) and restore it again (you may need to reset the ipod before doing this)
My iTunes had also told me that my ipod was corrupted a couple of times. Hope this helps everyone.