Over at github troubleshooting page, there is some info about this issue, but since I haven’t used this way of authentication (public key) previously it took me a while to figure out why exactly I kept getting this message and why I failed to establish a connection with github. The thing is, I generated an RSA key-pair with a name different from the default “id_rsa” and because of that the ssh-agent did not have the key in its cache (thus I could not authenticate).
To fix this, you can either use the default “id_rsa” for your key name (in which case it will be in ssh-agent’s cache automatically) or use “ssh-add your_key” command to add it to the cache.
If you did the same funky key-naming thing as I did, I hope this helps and takes away your headache! =D