Problema:

Al intentar hacer un push con git a un repositorio remoto de gitlab.com, se obtiene un error de acceso debido a autentificación fallida.

Permission denied (publickey).
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

Solución:

Definir el protocolo del repositorio remoto con https en vez de ssh. Para ello desde el menú de administración del proyecto en gitlab.com, obtenemos la dirección del repositorio del proyecto, seleccionado HTTPS en el menú desplegable:

Pongamos que la dirección del repositorio que hemos obtenido es:

https://gitlab.com/pepito/proyecto.git

Y usamos esa dirección a la hora de definir el remote local (que llamaremos or ejemplo 'repohttps') que usaremos al hacer el push:

git remote add repohttps https://gitlab.com/pepito/proyecto.git

Si ahora revisamos los remote que tenemos, entre ellos estará el nuevo con la dirección https que indicamos:

git remote -v
... (probablemente otros remote que tengamos)
repohttps https://gitlab.com/pepito/proyecto.git
... (probablemente otros remote que tengamos)

Ahora al hacer push, usaremos el remoto que acabamos de crear, para conectar a través de https.

git push repohttps

Con ésto (a mí) ya no se me queja de fallo de autentificación, y hace el push (sube las cosas al repositorio remoto) sin problemas.