I am currently on a vacation in Portugal and bought a local sim card for a Samsung Galaxy S4 with stock ROM. Now I cannot access any google services anymore. The rest of the internet works fine but any site using google's cdn fails to load. Android of course is almost impossible to use. Interestingly enough it only affects google.com, other google domains work fine.
I did originally receive an email from google claiming a suspicious login. I verified that it was me on their security page on another phone. I tried resetting the dns cache, change the dns servers, the google unlock captcha, ... nothing works. It works fine when I log in via Wi-Fi. If I share the connection with a tablet that tablet can access anything just fine. Deleting and recreating the google account on the phone also does nothing.
I am at a loss of what to try next. Any ideas? Thanks!