Upgrading my 3GS to iOS 5.1.1, I lost all my apps After backing up my iPhone 3GS and then updating to the new iOS 5.1.1, I lost all my apps and saved notes/data. How can I get all the apps back?
When I first updated to iOS5 I lost all of my apps too.  Interestingly, it had the spinning sync icon at the top of the phone for a few hours after as it manually downloaded all of the apps.  They suddenly appeared one after another.  Perhaps it's doing this.

Try downloading an app that you had and see if it still has the settings/saves it had.  If so, I'd expect this is the case.