From tech note
http://support.apple.com/kb/TS1275:
+*Error 1004 and 1013:* This error may be the result of the connection to gs.apple.com being blocked, redirected, or interrupted. Adjust your hosts file or security software to ensure that connections to gs.apple.com are not blocked. If the issue persists, try restoring on another computer with a known-good connection. If this restore is successful, you will need to contact whoever supports your install of the operating system and security software installed on your computer for assistance. If your hosts file redirects requests to gs.apple.com, you may choose to follow Can't connect to the iTunes Store, in the "The 'hosts' file may be blocking the iTunes Store" section.+
One possible cause of this is if you have ever used a program that modifies the iPhone boot process, such as tinyumbrella. Another is your security software is blocking the connection.
