The instructions here:
http://support.apple.com/kb/TS1275 ask you to try doing the restore as a different user. This is a round about way of telling you the iPhone2,<version>_Restore.ipsw file is corrupt.
Try closing iTunes, renaming this file, and restarting iTunes. This will force a new copy of ipsw to be downloaded & hopefully get your phone restored. Worked for me.
Locations for the ipsw file from the knowledge base link above...
Mac OS X
iPhone: ~/Library/iTunes/iPhone Software Updates
iPod touch: ~/Library/iTunes/iPod Software Updates (The tilde "~" represents your Home directory.)
Windows XP
iPhone: C:\Documents and Settings\[username]\Application Data\Apple Computer\iTunes\iPhone Software Updates
iPod touch: C:\Documents and Settings\[username]\Application Data\Apple Computer\iTunes\iPod