OK ... I had the same problem as everyone else, my 4S was stuck on the "slide to update" screen. Actually it was stuck at multiple other points too, but in each case a (repeated) reset (i.e. hold power+home down till screen goes black) seems to kickstart the update over the various roadblocks.
So re the slide to update freeze, keep in mind the phone was connected to the computer the whole time. Also I deactivated the computer firewall, just in case the verification process was using my PC connection.
This time when I did a hard reset, I was now prompted to key in password, and this sent me to the Apple logo update screen that I had been stuck at the last few times, again at about 25% completion, only this time the polarity of the screen was reversed (i.e. black logo on white screen). Still stuck at 25% no movement, till I noticed that on the PC iTunes, I had gotten an error message saying PC could not detect iPhone.
I clicked Try Again,
Suddenly, the phone update bar jumped from 25% to about 66%, and then rapidly completed, rebooted, and viola fully updated.
Maybe I got lucky. Best of luck to you all!