git push heroku master; server sent publickey

Recently I have been having some trouble with heroku git push from my Windows PC. Whenever I run,

> git push heroku master

I an stung with this message:

PuTTY Fatal Error
No supported authentication methods available (server sent: publickey)

I have tried several things like adding keys with heroku keys:add etc.
Finally, following helped:

> heroku git:remote -a appname

Apparently, meta about remote was corrupted, and executing this command fixed it.