This error was pretty hard to solve. I emailed heroku support and they recommended:
bq. For git commands to work git needs to use the ssh key associated with that account. It's probably choosing a key associated with a different account which is causing these permissions errors. You can use a ~/.ssh/config file to specify which key should be used. Check out this client plugin written by one of our engineers. It helps manage both Heroku credentials and ssh keys for easy switching between accounts. https://github.com/ddollar/heroku-accounts Please let me know if you have more questions.
Their comment did make my future work with multiple accounts easier -- it didn't solve my problem which was that my old fingerprint was still active, and causing trouble.
The solution for me was not to create and provide a new key to heroku. It was to go to the gnome passwords and keys folder and manually delete "My Personal Keys".
See this comment from "launchpad":https://bugs.launchpad.net/ubuntu/+source/openssh/+bug/505278 for details.
bq. The culprit is gpg-keyring-daemon. It subverts the normal operation of ssh-agent, mostly just so that it can pop up a pretty box into which you can type the passphrase for an encrypted ssh key. And it paws through your .ssh directory, and automatically adds any keys it finds to your agent. And it won't let you delete those keys. How do we hate this? Let's not count the ways -- life's too short.
bq. The failure is compounded because newer ssh clients automatically try all the keys in your ssh-agent when connecting to a host. If there are too many, the server will reject the connection. And since gnome-keyring-daemon has decided for itself how many keys you want your ssh-agent to have, and has autoloaded them, AND WON'T LET YOU DELETE THEM, you're toast.
bq. What you really want to do is to turn off gpg-keyring-daemon altogether. Go to System --> Preferences --> Startup Applications, and unselect the "SSH Key Agent (Gnome Keyring SSH Agent)" box -- you'll need to scroll down to find it.
bq. You'll still get an ssh-agent, only now it will behave sanely: no keys autoloaded, you run ssh-add to add them, and if you want to delete keys, you can. Imagine that.