When i installed iOS5 on my iPhone 3GS yesterday all non-native apps would crash. I read somewhere about an issue like this in earlier betas. The solution was to download a new app (any app).
I went to the app store on my phone, found a random free app to download, and as soon as the app started downloading (before it even finished), all the other non- native apps started working.
This also seemed to resolve an issue with iTunes only showing "Other" for the things that were using memory on the iPhone.