I know this is an old question but I just ran into this problem and had to do quite a bit of troubleshooting to finally fix it. Thought I'd post what I did in case others are facing the same difficulty.
This is what I did to resolve the issue on mac.
Uninstall and re-install Heroku
$ rm -rf ~/.heroku
$ sudo rm -rf /usr/local/heroku /usr/bin/heroku
Download the latest Heroku CLI (formerly the Heroku Toolbelt)
https://devcenter.heroku.com/articles/heroku-command-line
Login
$ heroku login
You may need to check that your ssh-key is ok now.
$ ssh-keygen -t rsa
Next, run the following to be sure to add your local ssh-key to Heroku.
$ heroku keys:add
Log out and back in to Heroku. (note this is not standard heroku login). I'm not sure exactly why this is different but it worked for me.
$ heroku auth:logout
$ heroku auth:login
Make sure a Heroku remote git is associated with the project. In my case I had to add as follows:
`$ heroku git:remote -a <my-app-name>`
Where <my-app-name>
is the name of the app already instantiated on Heroku. If you don't have one login to Heroku site and set up a new app.
I then did a standard git add and commit.
`$ git add .`
`$ git commit -am "fixing heroku connection issue"`
Generate a new Heroku auth token. This seems to be the crucial step.
`$ heroku auth:token`
This should return a long auth-token
made up of letters and numbers.
Try the push again but use the generated auth-token
for password if prompted:
$ git push heroku master
Username for 'https://git.heroku.com': <your-username> or leave blank
Password for 'https://git.heroku.com': <auth-token>
If everything has worked it should build and push the app to Heroku.
Some of these steps might not be necessary or may have to be done in a different order. Don't be discouraged if it doesn't work first time. I had to take a couple of shots at it to get it working. Hope that helps!