Expo - The recipient device is not registered with FCM. Android specific device sdk40

I’m getting the following error in when sending Expo push notification to a specific Android user.

The notifications are all allowed in app settings.
Standalone app
Expo sdk 40

It worked on their previous device, they got a new device and new install and now that new device doesn’t receive the notifications. Other Android and IOS standalone’s do get notifications just fine.