Did you boot into recovery or just plug it into iTunes? I've seen that and booted into recovery mode by having the device off, hold the home button as you plug it into your computer and it should boot to the connect to iTunes screen. Also try kicking off the restore and then disconnecting from the internet. I've been having issues lately with software updates through iTunes failing when it tries to confirm with iTunes but when I disconnect the wireless just after kicking the restore off, it works every time.