¿Por qué sólo recibo notificaciones push cuando enciendo el teléfono?

Lo más probable es que esto se deba a un ajuste que pretende reducir el uso de la batería y del servicio apagando la conexión de datos y/o wifi mientras no estás usando el teléfono.

Hay algunos ajustes que debes alternar:

1: Settings -> Power -> Sleep Mode
Esta opción está activada por defecto y hace que el dispositivo desactive la conexión de datos durante los periodos de suspensión más largos, es decir: Cuando la pantalla esté apagada durante un tiempo se apagarán los datos ( esto incluye el wifi ) y no podrás recibir más notificaciones.

2: Settings -> WiFi -> Menu -> Advanced -> Keep Wi-Fi on during sleep
Cambia esto por Siempre - Otras opciones son "Nunca" y "Sólo cuando está enchufado" (al cargador). Si no está configurado en "Siempre", el teléfono hace lo mismo que arriba. Esto es sólo wifi.

3: Settings -> More -> Wireless & networks -> Usage -> Menu
Aquí, desactiva la función "Restringir datos en segundo plano". Dependiendo de tu versión de Android puedes elegir en detalle qué aplicaciones quieres permitir en segundo plano y cuáles no. Las aplicaciones a las que no se les permite una conexión a Internet en segundo plano no recibirán notificaciones.

4: En caso de que estés usando un ahorrador de energía (En mi caso: Settings -> Power -> Power saver ) deberías comprobar también la configuración de la misma. El mío tiene la opción de "Poner la conexión de datos en reposo cuando la pantalla está apagada" - Si tienes esa configuración deberías desactivarla también.

Ten en cuenta que los nombres de tus ajustes pueden diferir ligeramente de los míos (por ejemplo, "Energía" podría llamarse "Batería" y tus ajustes de "Uso de datos" podrían estar en otro lugar), así que puede que tengas que buscar un poco, aunque la función que estamos buscando debería llamarse igual.