You can go to Credentials page of Google Cloud console and manage credentials of all your projects.
In my case, I needed to remove a credential that had caused the conflict (WARN: For caution, download it before removing it. Or just modify it).
If you deleted your firebase project recently (like me), see: https://stackoverflow.com/a/45270281/5318303.
See this for more information or other cases: An OAuth2 client already exists for this package name and SHA-1 in another project
It looks like the Firebase assistant in Android Studio at the moment only works when creating new Firebase projects and not updating existing connected Google Projects.
When selecting the IMPORT GOOGLE PROJECTS on the Firebase console page, it did autogenerate a new OAuth 2.0 client ID for the project credentials on the Google Developer console page. The project had an existing credentials for this, so maybe some conflicts there?
Deleting this new autogenerate credentials and creating a new project instead fixed the issue with the assistant and the message in Android Studio is now:
Firebase project created and connected locally to module: app.
This happen to me, when I changed into prod Firebase (Google) account.
What happen is, I changed the package name and forgot to update the gradle file.
Under defaultConfig update the applicationId into your new package name.
Delete your current google-services.json and reconnect to your firebase (using Android Studio Firebase console)
If in any case you cannot delete your google-services.json, comment your Firebases dependencies on your gradle file then sync. Then delete it.
Take note, No clients were able to be added to your Firebase project for the following reasons: An app with this package name and SHA1 is already connected to a Google project. If you have used a Google API previously, please select that project in the Connect to an existing Project list. error happen when your applicationId is already connected to existing Firebase account. You do not necessary need to delete to previous Firebase account, just update your applicationID. This error almost made me jump into 50th floor. So save your self, if you run into this error ask here. Cheers mate.