For me it gave the same error of:
Please make sure you have the correct access rights and the repository exists.
A quick fix was to eliminate the ~/.ssh/config file
mv config config_old && touch config
eval "$(ssh-agent -s)"
git clone your_repo
As it turned out to be the config file that was corrupt and configured with two ids