OK I just managed to fix my iphone 3gs. Heres how I did it without jailbreaking. Just to make sure we're all on the same page here:
updating an app using wifi / 3g = not working (cannot connect to itunes store)
fix suggested by poster = not working (removing all apps – need to restore file)
installing a free app from appstore on both wifi/3g = (not working, could not connect to itunes store)
signing out / in = not working
signing out / in from settings = not working
First thing I did was sign out of my itunes account on my computer. This screwed the pooch even more as I could then not log in to itunes store on my computer. I then opted to sign into my iTunes online support page at something like myinfo.apple.com or something. There I changed my email address to something shorter, mainly because I was sick of typing a long one in every time I wanted to attempt to sign in! Whilst it changed online, iTunes had a hiccup. I have a pleasant screenshot of itunes telling me that my email address has been verified whilst simultaneously giving me a pop up telling me that I could not log in due to my email address not being verified...fun!
After some emails back and forth with an apple support person I managed to get them to verify my email account. Now I could get back into iTunes on my mac, 1 step backwards, 1 step forward.
Next I made sure that all my account settings were correct, right address card details etc. Just so there wouldn't be any problems there.
None of this made any difference to my phone, from either the iTunes app or the app store all I would get were css-less versions of the apple site from all the software buttons at the bottom of the screen. When I tried to sign in through Settings I just got the joyful "Could not connect to iTunes store" message. Then the thought hit me that Game Centre required a sign in. Opened up Game Centre and there was my old email address, logged out of it and then logged into it using my new email. That all seemed to work easily, off I went to see if I could get into the app store. Nope, still no joy. A day went by, still no new news from apple, (waiting on a reply from their support again) I tried deleting all my apps since Christmas when I was last sure it was working, still no better. Then I thought I'd flick through the other apple apps and see if any of them required a sign in. First one I tried was iBooks. The sneaky little app has a link to it's own store doesn't it. It seemed to be working but with my old email address so I logged out, and logged in with my new address. Went straight to the app store and voila, it's working again.
Hope this helps someone, I was stuck for two weeks!
🙂