This frustrated me for 45 minutes tonight, and hopefully this post can save someone else from similar pain.

[MyRepo (master)]$ git push origin master Permission denied (publickey). fatal: The remote end hung up unexpectedly

I followed all the instructions at http://github.com/guides/providing-your-ssh-key and http://github.com/guides/addressing-authentication-problems-with-ssh and verified my connection was working via the ssh git@github.com command, but kept receiving the Permission Denied (publickey) error when trying to push to github. Eventually I stumbled onto a workaround. In your local repository, remove and re-add the remote link. These commands worked for me, but YMMV:

git remote rm origin git remote add origin <remote url>

Replace the remote url with your github clone url (looks like git@github.com:<username>/<reponame>.git) and try your push again.