For me, the error was due to my work android profile. I uninstalled the debug app in personal profile but it remained in the work profile, once I uninstalled it there and ran flutter run. It worked without any issues.
So,
First, ensure you deleted the App in both personal and work profile
And then run
flutter run
Update:
By profiles I meant, android user profiles on your phone.