Uninstall / reinstall of GCM solved the problem for me too.
My guess is that it has something to do with permissions for the GCM app in Android, but since I didn't check this prior to reinstalling I can't confirm it.
GCM has now got access to Calendar, Contacts, Position and Phone.
Stig