I think i am not the only one that ran into this issue trying to set up your app into Heroku. I was trying to do so as part of following the Ruby On Rails tutorial and ran into this issue in which i sank a couple of hours. I am running on Ubuntu 11.10, and had already set up my id_rsa and id_rsa.pub keys for Github in ~/.ssh. so when I called in a terminal

heroku login

and provided my login credentials, it told me that it found my public key in ~/.ssh and uploaded to Heroku. All is fine then, but when I ran

git push heroku master

No luck there, I kept getting a :

“Permission denied (publickey). fatal: The remote end hung up unexpectedly”

After deleting my original app I had set up on Heroku, deleted my original keys and setting them up again in Github, i noticed that, contrary to before when setting up keys by running

ssh-keygen -t rsa -C  “myemail.com”

I was asked now in which directory i wanted to save the file, with the default being set to /root/.ssh/id_rsa. That was the rub! Even though Heroku picked up my public key residing in ~/.ssh, when running the git command it was still looking for it in /root/.ssh. I just copied over the keys in ~/.ssh to /root/.ssh and lo and behold, I had a working push again!

I then ran into another issue whereas, having deleted my original Heroku app, my git remote was now invalid. I had to point my git remote to a working app on Heroky. In Git to change your remote, not deleting it but just updating the url to a new one, run:

git remote set-url heroku git@heroku.com:example-app-872223.git

Hope it helps!