Upgrading my 3GS to iOS 5.1.1, I lost all my apps
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.