This has been a sporadic problem since the old C2DM days. We request a registration ID, we receive a registration ID. We send the registration ID to our backend server. The backend server pushes an acknowledgement to device. All seems well from the server side but the message never arrives back at the device. Or sometimes it arrives 5-90 minutes late. We have developed a bag of tricks seems to have a 100% resolution rate on pre-ICS devices. ICS and above has been more problematic. And now I have one user on 4.1.1 where nothing we try seems to work.
Their phone is not rooted
They have uninstalled and reinstalled our app multiple times
Device has been restarted multiple times
Our app cannot be installed on the SD card
They are trying this with a good WiFi connection to avoid possible new restrictions on mobile carrier data networks
Anyone have any other ideas we can try???
FWIW, the pre-ICS instructions we use to resolve this issue are
Go to the home screen and select Menu > Settings > Accounts and Sync
and make sure Background Data and Auto-Sync settings are enabled. While
you are here, press the Google account setting and Sync Now.
Request a secret app feature that unregisters the current GCM registration and requests a new one
Restart the device and try again.
Power down your device, remove the SD card, then power it up and try again. I have no idea why this would make any difference, but it got one user up and running.