What worked for me was unplugging my router and then plugging it back in after a few seconds. It was one of the recommendations listed in the Apple troubleshooting forum:
http://support.apple.com/kb/TS1368
I've had my iPhone 4 for almost a year and just today I started getting that "Cannot connect to iTunes Store" message when I tried updating a few of my apps. I tried shutting off my phone, I verified that I had the latest iOS, and I toggled the on/off button in my wireless settings on the phone, but none of that worked. I didn't want to reset my phone or sync it to iTunes so I googled it and came across the link above. I didn't think that my router was the problem because my internet was working just fine on my iPhone and the signal strength was good. But as soon as I unplugged my router and plugged it back in, I tried updating my apps again and sure enough, as soon as I entered my password, the apps began updating immediately. Really weird. Maybe this will work for some of you.
Another issue I've had is when I'm somewhere that doesn't have WiFi, it won't allow me to update or download apps that are over a certain size. Sometimes it'll give me the message that I need to connect to WiFi because the app is over certain MBs in size, and sometimes it won't say anything at all and it just won't download. But as soon as I connect to WiFi, it will.