For anyone coming across this who is using Flutter and Google / Firebase Auth and they encounter this when they go from local device / emulator testing to Google Play, this occurs because the SHA1 fingerprint is now different as Google Play takes care of signing your app for distribution for Play Store.
Solution - Get the new SHA1:
Go to Play store and select Your App
Go to Test and Release
Go to App Integrity
Scroll to Play App Signing (click settings to the right of the title)
Copy the SHA1 fingerprint
Go to Firebase Project Settings or Google Auth console where you define your SHA certificate fingerprints and add the new SHA1
Gets me every time.