Android studio después de cambiar el nombre del paquete que arroja No se ha encontrado ningún cliente coincidente

Has añadido el complemento de Google Play Services al proyecto, que se lee desde google.json encuentra en el módulo de la aplicación.

google.json contiene datos de configuración del servicio, como Google Project ID, nombre del paquete de aplicaciones, etc.

Dado que el nombre del paquete de aplicación también se almacena en ese json, no coincidirá más, tienes que generar un nuevo json en este sitio (esto es para GCM).

Luego reemplace el google.json en su proyecto con el que ha generado.

Busque los nombres del paquete y el proyecto creado en firebase debe ser el mismo

Tuve el mismo problema cuando cambié el nombre de mi paquete. He creado un nuevo proyecto Firebase desde la consola firebase y he descargado el nuevo archivo google-services.json de la consola firebase y lo he reemplazado por el antiguo, pero aún así tengo el mismo error. Entonces comprobé mi archivo de build.gradle (App) todavía tenía el nombre anterior del paquete así que lo cambié con el nuevo nombre del paquete y trabajó.