creo que se lo que te pasa, ya que me pasaba algo parecido, aun teniendo tarifa de datos, no me llegaba las notificaciones a menos que yo las actualizara en el programa (tuenti, gmail, etc)
Lo que hice es en el escritorio/pantalla inicial al desbloquear, añadir la barra donde puedes acticar/desactivar wifi, bluetooth, gps, sincronizacion y brillo (en ese orden). El penúltimo, si esta activado, te llegan las notificaciones (activas la sincronizacion de programas creo) si no lo esta, pues no te llegan esas notificaciones.
Espero haberte ayudado, si no es eso dimelo, saludos