FCM token invalidated when app is updated

Question

I am testing FCM within my Xamarin.Forms.Droid app. I have a small problem though: Whenever I update my app (build a new version and install it to my phone via Xamarin Studio), the registration id is invalid.

When I reinstall the app, I get a new registration id which works perfectly fine. But, once again, when I update my app, the registration id stays the same but FCM does not longer accept it and returns this:

    {
  "multicast_id": 7779985059157799056,
  "success": 0,
  "failure": 1,
  "canonical_ids": 0,
  "results": [
    {
      "error": "NotRegistered"
    }
  ]
}

Anyone knows how to fix this?