I recently was trying to upgrade my iPhone to the 4.3 beta software, when I kept getting the 1013 error from iTunes towards the end of the restore process. I finally found out why iTunes couldn't connect to the Apple servers.

Apparently Cydia modifies your host file to redirect gs.apple.com to their servers. If you don't undo that modification, your iPhone cannot connect to Apple.

To correct this, open Terminal. Enter "sudo nano /private/etc/hosts," enter your password, and comment the line refering to gs.apple.com. The results should be similar to below. Hit ctrl+x and then Y to save.

##
# Host Database
#
# localhost is used to configure the loopback interface
# when the system is booting. Do not change this entry.
##
127.0.0.1 localhost 
255.255.255.255 broadcasthost
::1 localhost
fe80::1%lo0 localhost
#127.0.0.1 gs.apple.com
#74.208.10.249 gs.apple.com

Then try the restore again.