After playing with the phone a little more I noticed that every time I opened App Store app I got the same message about not being able to connect to the App Store. Once the app was started I could navigate the Featured, Charts, etc. links but the initial error message always (and annoyingly) popped up.
Turns out this is a common error that people are experiencing and the discussion boards at discussions.apple.com are all atwitter. While the solution below may seem bizarre it does seem to do the trick. The nature of the solution suggests to me there is some kind of certificate issue at play but the details of that don't really matter.
- Go to Settings -> General -> Date and Time and turn OFF "Set Automatically"
- Set the date 2 or more years into the future
- Go back into the App Store app where you will get the same error message. No matter.
- Go back into Settings -> General -> Date and Time and turn "Set Automatically" back ON
Now you should be able to successfully launch the App Store app without the error message. You will likely get a message about a certificate not being recognized or being out of date. Just touch the Continue button when that comes up.