Had the same issue. I was trying to add my public ssh key to the git repo itself, but I still wasn't allow to push.

Once I added the key to the account itself, everything worked just fine.