So my dad and I just upgraded to the 5, but I noticed that when I updated his iphone software it stuck to the "Connect to iTunes" screen (aka, what brought us all here), so I decided to forego updating my own iPhone software. I was updating his iPhone on his laptop (HP: Windows 7) and mine on my MacBook.
After coming here, I realized the problem was in the restoration
WHAT WORKED FOR ME:
After an hour or so of trying to get my dad's phone unstuck, I decided to just plug it into my computer. iTunes detected it as having been in the middle of a restore, and prompted me to finish the update/restore (I think...from what I can remember). All I really wanted was for the phone to not be stuck on that forsaken screen, and it worked! When it was all done restoring on my laptop, I ejected it and plugged it back into my dad's computer to finish the restore (from his previous backup).
Anyway, just wanted to post what helped for me. Hopefully it helps for people who have access to another computer with iTunes!