Play and Maps not working while Browser works fine

[yeseanul]

Hello,

Background
Couple of weeks ago I've noticed connection problems when using data. While some apps worked OK (e.g., Chrome), others didn't (e.g., Google Maps, Google Play); this also happened with non-Google apps.
So Chrome loaded everything without a problem. Maps, let's say, took 5-10 minutes to return a search result and even more than that to load a map area. Google Play took forever to search for something, often replied with a "connection problem" message and when trying to download an app, the speed was ~10kbps.
A seedtest.net test returned each time ~1000kbps.
Contacted Google and after several emails, the only solution seemed to be a Factory Reset. Which I did.

Now
Running only stock Android apps. The problem is still here. I've manually configured the APNs and set the Notwork operator either manually or automatically. Data is enabled. And the mobile network state is connected.

Unlocked Samsung Galaxy Nexus
Android 4.2.1

Hope that somebody has an idea. Looking forward to your replies.

Thanks,
Alex