Do you have any security software installed? If yes, make sure iTunes can connect to Apple during the restore process:
http://support.apple.com/kb/TS3125
If this does not help, delete the ipod firmware file (*.ipsw) on your computer, located C:\Documents and Settings\username\Application Data\Apple Computer\iTunes\iPhone Software Updates to make iTunes download a new copy when you connect again in recovery mode. Maybe the file on your computer got damaged. Also make sure to run the latest version of iTunes (9.2.1).
Good luck.