Hard to say for sure but it sounds like a problem with the internet connection you're getting from your operator. Would it be possible for you to try if it works when the phone is connected using WiFi instead?
You could also try removing your operators proxy/port from the internet settings under Settings -> More -> Mobile networks -> Access point names and see if that helps.
