On a 4S with iOS 5, JR's procedure - modifying the DNS and Search Domains data - resolved the problem for me. Thanks, JR!
(The problem on my device only occurred with the App Store app. All the other apps were able to connect fine over wifi - including iTunes. In over a year, this is the first time I've encountered this issue. Whether a coincidence or not, it cropped up just after I tried to access the App Store after an iTunes sync using a Mac Pro.)
Logging out and back in from the Store did not correct the issue, though it's definitely worth a try as it seems to have helped others here in some instances. I recommend logging out, then in, as a first step, and updating the DNS and Search Domains as a second step.
I haven't tested to see, but I wonder if reverting all Settings isn't simply a broad brush method of addressing the DNS setting (along with a host of others)? Hopefully most folks can avoid having to resort to this.