Hola
He tenido problemas con Android 5 en Nexus 4 y 5 en el alta de mensajes Push, y sin embargo en otros modelos de moviles con el mismo S.O. no, asi que ya empezando por ahi creo que existe algún tipo de problema con esos Nexus y Android 5 (Samsung ha tenido que retirar su firmware para S4 por que no iba casi nada).
Para cosas generales con Android 5, te recomiendo que compiles con al menos B4A v3.82, y tambien que añadas al manifest esto:
SetApplicationAttribute(android:theme, "@android:style/Theme.Holo")
Se que no tiene que ver con tu servicio, pero si estas trabajando con un Nexus y Android 5, en algún momento te surgirá otro problema que con estas dos cosas las corregirás.
Saludos: