I had the same issue when i updated my iPhone 4 yesterday. Here is how i was able to resolve it:
- Open AppStore from your iPhone/iPad
- Install ANY app (free apps works just fine)
- In the process it asks for your AppleID, enter it. (In a way that's validating the new iOS for use with your Apps.)
All apps should work now.
(minus the apps you installed using someone else's AppleID -if you have any- Those just went away on my iPhone because of the new restrictions)
Hope this helps..