I had the same problem, all I did was fix the date and time on my iPad and it worked! Weird I know but my problem was solved! If your date and time is right try switching the date and then switch it back. Good luck!
Check the hosts file. The restore will fail if there is an active entry to redirect gs.apple.com. Follow iTunes: Advanced iTunes Store troubleshooting to edit the hosts file or revert to default on Windows. See section "Blocked by configuration: (Mac OS X/Windows) > Rebuild network information".
Try to restore from another known-good computer and network.
If the errors persist on another computer, the device may need service.