iPhone Unable to use any Apple Services on 3G

Has anyone been experiencing problems in download/updating apps or using iTunes Radio on 3G or cellular data for that matter? It seems after updating to iOS 7, I haven't been able to use iMessage, FaceTime, download/update apps, use iTunes Radio or buy in-app purchases when using 3G on my iPhone 5. I really doubt it's my cellular data speed as I'm able to watch Youtube without buffering on it. I'm also able to download in-app things like Fifa 14 Rosters or PvZ 2 update.

I've tried logging off iCloud, FaceTime, iMessage and Appstore, but it won't let me sign back in. Heck, it won't even let me log off iCloud. I've also tried Reset Network Settings and Reset Settings, but nothing seems to work. I hate the thought of having to clean install the OS and still end up with the problem. Any suggestions would be appreciated.

Thanks!

moonman239 said:

Before anyone helps you, please answer a few questions.

1) What do you mean by not working?
2) Do you experience any problems attempting to do the same tasks over a WiFi connection?
3) What is the name of your carrier?

Click to expand...

1) Apps wont download, iMessages wont send and iTunes Radio Music wont start.
2) Nope. It works fine on WiFi
3) It's a carrier from the Philippines, Sun Cellular. No LTE, just 3G for this network

Yes I am. I noticed that it only doesnt work when it has to go through Apple's servers. Everything else seems to be working fine.