Since iOS 6 was officially released yesterday, several bugs have been reported, including issues with Wi-Fi, Passbook, and battery life (although Apple has apparently fixed the Wi-Fi bug). Some users are also having problems connecting to the iTunes Store, which is probably insanely frustrating because the first thing you want to do with a new OS is try out new apps. Luckily, there's a way to fix this by tweaking the date and time settings.
Open Settings, then go to General >> Date and Time. Switch the Set Automatically option to Off, then set the date one year ahead. Try to open the App Store again, and if you get another error message, go back and correct the date by switching Set Automatically back to On. Now you should be able to connect with no problems.
This may not sound like much of a fix, but quite a few users have reported that it works, and some even say it also helps with the Passbook issues. Now you can get back to more important things, like getting Google Maps back.