It turns out that new versions of Firebase SDKs depend on a new internal infrastructure service, called FIS (the Firebase Installations Service) for targeting identifiers ("FIDs" or "Instance-IDs").
If you are using API key restrictions for the API keys you use in your application, you will have to extend those restrictions to allow usage with the new Firebase Installations Service at firebaseinstallations.googleapis.com.
To allow your API key in question to be used with the new Firebase Installations API:
go to the Google Cloud Console
choose the relevant project (i.e. the project you use for your application)
open the menu and go to APIs & Services -> Credentials
click Edit API key for the API key in question
scroll down to API restrictions
from the dropdown, choose Firebase Installations API
click Save
wait a couple of minutes for Google servers to update and retry...