Localytics Firebase Push Notifications are not working on Xamarin Forms for Android

Question

I've managed to get this working in the past, but its suddenly stopped working and I don't know what to check in order to get it working again. I am trying to get push notifications working using Firebase Cloud Messaging through Localytics. I am testing using the Localytics Rapid Push Notification Test module. The device pairs ok but when I send the notification nothing happens on the device.

1) I've regenerated my google-services.json file and pasted into the root of my folder.

2) I'm pretty sure my Android Manifest is fine:

<meta-data android:name="LOCALYTICS_APP_KEY" android:value="{HIDDEN FROM STACK OVERFLOW}" />
<activity android:name="com.localytics.android.PushTrackingActivity" android:exported="true" />
<receiver android:name="com.localytics.android.ReferralReceiver" android:exported="true">
  <intent-filter>
    <action android:name="com.android.vending.INSTALL_REFERRER" />
  </intent-filter>
</receiver>
<receiver android:name="com.google.firebase.iid.FirebaseInstanceIdInternalReceiver" android:exported="false" />
<receiver android:name="com.google.firebase.iid.FirebaseInstanceIdReceiver" android:exported="true" android:permission="com.google.android.c2dm.permission.SEND">
  <intent-filter>
    <action android:name="com.google.android.c2dm.intent.RECEIVE" />
    <action android:name="com.google.android.c2dm.intent.REGISTRATION" />
    <category android:name="{HIDDEN FROM STACK OVERFLOW}" />
  </intent-filter>
</receiver>

3) My implementation of FirebaseInstanceIdService gets called ok as I can debug it:

[Service]
[IntentFilter(new[] { "com.google.firebase.INSTANCE_ID_EVENT" })]
public class MyFirebaseIIDService : FirebaseInstanceIdService
{
    const string TAG = "MyFirebaseIIDService";
    public override void OnTokenRefresh()
    {
        var refreshedToken = FirebaseInstanceId.Instance.Token;
        Log.Debug(TAG, "Refreshed token: " + refreshedToken);
        Localytics.PushRegistrationId = refreshedToken;
        SendRegistrationToServer(refreshedToken);
    }

    void SendRegistrationToServer(string token)
    {
        // Add custom implementation, as needed.
    }
}

4) My implementation of FirebaseMessagingService never ever gets called!

[Service]
[IntentFilter(new[] { "com.google.firebase.MESSAGING_EVENT" })]
public class MyFirebaseMessagingService : FirebaseMessagingService
{
    const string _tag = "MyFirebase";
    public override void OnMessageReceived(RemoteMessage message)
    {
        Log.Debug(_tag, "Remote Message Received");
    }
}

5) In my MainActivity I am calling Localytics.RegisterPush(); within the OnCreate() override.

Can someone please help? Thanks in advance!