heroku fatal: could not read from remote repository. please make sure you have the correct access rights and the repository exists.

I had the exact same error (on windows 7) and the cause was different. I solved it in a different way so I thought I'd add the cause and solution here for others.

Even though the error seemed to point to heroku really the error was saying "Heroku can't get to the git repository". I swore I had the same keys on all the servers because I created it and uploaded it to one after the other at the same time.

After spending almost a day on this I realized that because git was only showing me the fingerprint and not the actual key. I couldn't verify that it's key matched the one on my HD or heroku. I looked in the known hosts file and guess what... it shows the keys for each server and I was able to clearly see that the git and heroku public keys did not match.

1) I deleted all the files in my key folder, the key from github using their website, and the key from heroku using git bash and the command heroku keys:clear

2) Followed github's instructions here to generate a new key pair and upload the public key to git

3) using git bash- heroku keys:add to upload the same key to heroku.

Now git push heroku master works.

what a nightmare, hope this helped somebody.