I was a little nervous for a while that I put my phone into a useless state but then I figured it out with a little help from this forum. Thanks! Let me tell you my story and hopefully it will help someone.
I had the same error 1013 after a botched upgrade to 4.2 running the itunes 10.1 Beta. I tried to use Tiny Umbrella to exit the recovery mode but was unable to successfully do so. It just kept rebooting to the plug into itunes screen.
I then attempted to revert to iOS 4.1 but was met with another error 1004 on restore. At this point I thought I was screwed. I then used TinyUmbrella again to exit recovery mode which worked. Good news, I was set back to useable 4.1 iPhone.
For whatever reason I wanted to give it one more try so I upgraded to 4.2 again. Same error 1013

, however, I this time I was able to use TinyUmbrella to successfully exit recovery mode which allowed me then to restore my backup to the phone.
I'm happy I stuck with it. The airplay integration in 4.2 is sick! I now can easily use a Airport Express to stream podcast to areas of my apartment like the bathroom etc. with ease. Love it! Airplay for audio works anywhere there is an audio slider. iTunes store streaming, Pandora, Remote App, you name it. Great addition to an already amazing phone. I'm now really interested in the new AppleTV and the upcoming AirPlay equipped third party speakers.