iPhone 4S not connecting to iTunes Store using 3G, iOS 5.1.1

[ElectronicTech]

Hey guys, I have been running into this problem for a while now. I try to update apps on my 4S over the 3G network, but for some odd reason it says "cannot connect to itunes store". It'll work over wifi without any issue most times (sometimes I have to change the DNS to 8.8.4.4 but that is the least of my concerns). I can use safari and everything else normally, but it is just itunes.

I have tried various steps to fully resolve this, as indicated below:

Turned off my 3g and turned it back on - no change
Signed out and signed back in to iTunes over the phone - no change
reset network settings - no change
reset all settings - no change
change password - no change

The weird thing is, this cause is intermittent in the fact that sometimes it works, sometimes it does not. I have had a weird instance that I take and shut my phone off at night while on the charger and the next morning, poof it is working again

Anyone have any ideas to fix this issue? Thanks.

[ElectronicTech]

Update: Ironically not 30 minutes after posting this, it started working again! I was able to download two updates over 3g no problem. Only thing I did in settings was turn my bluetooth off due to my phone's battery draining like a sumgun and my phone warming up. Not related, but I guess the store is just flaky from time to time.