Just an FYI. I was running into this error, even though I swear the android app I was testing was built with the latest/greatest google-services.json file and I could send from the FCM console to the app.
I rebuilt the app after doing a Clean Project
and now I can send to the app with the FCM token it registers. So, maybe try a clean rebuild before beating your head against the wall for too long.