En mi caso cada vez que he restaurado de fábrica en cualquier terminal, tengo que cambiar la configuración de la propia aplicación de gmail.
Ajustes de Gmail > nuestra cuenta > Administrar etiquetas.
Aquí por ejemplo tengo activadas que se actualicen las etiquetas de Social, Promociones, Notificaciones y todo perfecto.