I tried like 5 times and no joy. Then I logged out/logged in and it worked. But took FOREVER! I got really nervous 'cause it said that it restored my iPhone to it's factory settings - never saw that before. Then took FOREVER to restore my apps and music etc. Not sure why the process changed, but it certainly took me for a loop. I'm finally on iOS 5 and it seems like it's working. I think it was having a hard time verifying the extract on the Apple servers due to the volume of upgrades, but that is only a guess.
You come in to iOS 5 and you have to set stuff up; just follow the prompts. I'm not on iCloud yet, so I entered my Apple ID. All seems well. Oh yeah: It seemed to have forgotten my Voicemail password too, so have that handy! I had to think hard about mine. I put that in and it all worked fine.
Doing my iPad 2 now. Then I'll go on to 10.7.2. After that, going to cut over to iCloud.
Hope this helps.