Bueno después de pegarme un poco con ello, lo he conseguido. El problema era la clave del Firebase, yo ponía la que he visto en los tutoriales en ingles clave de API de la web, pero a mi me ha funcionado poniendo la Clave de servidor que aparece en la pestaña de mensajeria en la nube. (Ademas te aconseja que utilices esa)
View attachment 53702
Tal y como muestro en la imagen.
Eso si he en mi base de datos he metido los token de los usuarios.
Lo cuento por si le puede ayudar a alguien