I was reading complaint posts on various blogs and websites while deciding whether to update. Here's an example, which points to a wider issue:
<< By LiquidD 5:09:17 PM PDT Oct 12, 2011
Reply to this comment
My experience had the same error on my iPad 1st gen, but a few more different error messages in the process. After installing iOS 5 it couldn't restore my apps, music or photos. After restoring from backup (with more errors) several times, I got all but my apps. Over 120 apps in set up certain places and special folders, gone. I had to install each app again and recreate all the folders again. It was good clean up but it took roughly 3 hours to finish. Definitely the roughest update I've had yet.
Glad my 4s will already have it installed. That was a pain. >>
If the cloud is working separately from upgrading to iOS 5, then a user like this should have had no trouble restoring his/her apps.