Facing "App not installed" error when trying to install flutter apk

Question

I am generating an APK file for the flutter app using:

flutter build apk

and it generates the following file:

build/app/outputs/flutter-apk/app-release.apk

I was always able to install this apk on my phone or any other phone to test it. But recently I started getting the following warning when installing the app:

And then when I tap "Continue", I get this error: "App not installed".

Since this error is new, I though maybe that's due to a change that I recently made. And the only change that could've affected the apk file is that I regenerated the key.jks file which is used to sing the apk file. That file is used in the android/build.gradle file:

    signingConfigs {
        debug {
            storeFile file('key.jks')
            storePassword '**********'
            keyAlias 'androiddebugkey'
            keyPassword '**********'
        }
    }

    buildTypes {
        debug {
            signingConfig signingConfigs.debug
        }
        release {
            // TODO: Add your own signing config for the release build.
            // Signing with the debug keys for now, so `flutter run --release` works.
            signingConfig signingConfigs.debug
        }
    }

What could be causing this error? I also tried "flutter clean" but that didn't help.