I was having this problem on my iPhone 4 iOS 5.1.1. If I went to the Apps store on my phone and clicked on Updates I'd get an error stating "cannot connect to iTunes store" but I was able to download new apps or even update apps if I did a search for the app and updated it from the apps page, it just wouldn't let me use the Updates page on the Apps store.
I read that it may be a WiFi issue even though I was clearly connected since I could download new apps. But I went ahead and tried using 3G instead of my WiFi and resetting the network connections and trying my WiFi again but the problem still occurred. I tried on another iPhone 4 that was connected to the same WiFi and it worked fine so I knew it wasn't my WiFi and the Apple update servers were working.
I tried resetting all settings from my phone and yep the problem was still there.
I didn't try increasing the date than setting it back but I did try turning off the auto date and making sure that it was the correct date and tried it with the manually set date, no luck, turned auto date setting back on and still I was unable to access the Updates page.
I tried turning the phone off and than back on.... You guessed it, still no updates page.
By this time I was frustrated and ready for bed so I opened iTunes on my PC and connected my phone, I figured I'd just try to get all of the updates through my PC and push them to the phone. Since I rarely use iTunes on my PC with my phone I clicked on my phone under Devices on the left hand side of the iTunes window than selected Apps from the menu for my iPhone. I was looking through to make sure all of my apps showed on this screen since there were a few I've added since I last synced with my PC, everything looked good and I couldn't find a update button on this screen so I clicked Apps from the menu on the left side of the iTunes window under the Library section and this made a pop up appear saying "You have changed the settings for the iPhone "iPhone 4". Would you like to apply these changes?", I figured this is to sync the new apps I've installed on my iPhone that weren't already on my PC's iTunes apps list so I clicked Apply. It starting syncing all of my apps from my phone to my PC, but since there were 116 apps I decided to sleep while it did this. Once I woke up I unplugged my phone and went on throughout my day, but before I left I clicked download all update from the PC's iTunes Apps page since I figured when I get home I'd go ahead and push the updates it downloaded while I was gone. Before I got home I decided ehhh why not try going to the Updates screen on my iPhone just to remind me why I got little sleep the night before and to my surprise it actually worked and showed that I had 26 apps which needed to be updated, but the Update All button didn't seem to work... So I decided to manually go in and update the programs one by one which thankfully did work now (I did a max of 3 updates running at the same time during this process). Once I got the total number of apps which needed to be updated down to about 9 (started with 26 apps that needed updates) I decided to try the Update All button again and FINALLY it worked and appears that my iPhone is finally working like it should be.
I don't know if it was a combination of the steps that I did that finally made it work or if it was just the syncing of my iPhones current apps with my PC's iTunes but I'm happy it finally works correctly. There's a chance that it could be caused by the number of apps that need updates since the Update All button was acting up until I got the total number down.... But I still don't know why syncing my phone's apps with iTunes on my PC would actually fix anything since I never actually updated any of the apps on my phone while it was connected to my PC, but if it works it works so I'm happy now 🙂