I had the same problem this morning. I was upgrading to 4.2 and ended up having to restore. I got the 1013 error and tried everything. I was on the phone with Apple for over an hour and tried a bunch of different things but couldn't it to work. They said that the error code meant that itunes couldn't connect to apples server. I ended up restoring on a different computer and it worked.
I had that issue myself. I forced my phone into DFU mode (turn it off, plug it in, hold the sleep button for 3 sec, then hold that plus the home for 10 sec, then release sleep and hold home for another 10) and it worked fine.