Had the same issue.
I had multiple public keys in my ~/.ssh/ directory: ~/.ssh/id_rsa.pub, ~/.ssh/id_rsa.gitlab.pub, ~/.ssh/id_rsa.planio.pub
I checked my public key in my SSH Keys settings section und gitlab.com and it matches my id_rsa.gitlab.pub key. So I thought everything should be fine. But still got the Permission denied error when try to push initial project.
Finally the problem was in my ~/.ssh/config file, where I wrongly put these lines:
# # gitlab # Host gitlab.com Preferredauthentications publickey IdentityFile ~/.ssh/id_rsa
Changed the IdentityFile to ~/.ssh/id_rsa.gitlab and sure it worked!