Are you sure you haven't restricted the background data/ apps. Option can be found in Mobile Networks.
Are you sure you are not using any proxy, make sure the APN settings are correct, data bearer, port etc
Have you tried to edit the host file, if you are rooted then trying edit it. Just put # before 127.135.184.234 android.clients.google.com. The IP you may see might be different.
If not rooted then delete the hosts file located in "etc" folder, reboot in recovery and wipe cache, reboot.
If non of this works, then i will be requiring logcats and complete phone info, just acquire a .apk of Phone Info app and post the screeshots.