Prueba abriendo manualmente la aplicación Google Play (los servicios, no el market) y forzando que quede abierta. Si con esto te sigue fallando, prueba la aplicación PNF (Push Notification Fixer).
A mi me pasaba igual que a ti, y con estas dos cosas ya no me pasa nunca.