Push Notifications not working over WiFi on Google Devices
It looks like GCM Push Notifications don't work with IPv6. I disabled IPv6 entirely in my router and now everything is fine. Though IPv6 was enabled for the past two years and I didn't have any kind of issue. Let's hope a Play Services update fixes it.