same exact problem.
After trying a number of times and checking all items listed here:
I have same error -
on a whim, tried to do it via a Windows iTunes install that was a new install -
i got the idea from an Apple page that asked if i was trying to "upgrade from my home machine or not"
it repeated locked the Win machine to death - figures - until i had to hold the button down.
Anyway, i see this reported elsewhere - I am going to the Genius bar tomorrow -
you will want to put you iphone in DFU mode and redownload a clean copy of ios 5. to do this connect your phone to your computer and open itunes. then hold down the sleep/wake/power button along with the home button for exactly ten seconds. after the ten seconds let go of the sleep wake power button but continue holding the home button until a popup in itunes tells you it has detected an iphone in recovery mode.(about 5 more seconds) then click to restore the softwear. note, when you iphone is in DFU mode the screen may be dark, this is normal.
hope this helps