Switching on the WiFi helped me to solve the problem. This is really strange - I don't have any WiFi hotspots that I connect to from my mobile, but still turning on the WiFi on my device helped me to overcome the problem. The guys at Google better start rolling out a fix for this bug at the earliest.