ssh access denied

It seems that hg push access works only irregularly. I currently get

{{{
LANG=C hg push -v
running ssh hg@bitbucket.org "hg -R loewis/openid2rp serve --stdio"
remote: Permission denied (publickey,gssapi-keyex,gssapi-with-mic).
abort: no suitable response from remote hg!
}}}

I double-checked that I have the right key uploaded, and, after re-uploading the key, a plain "hg@bitbucket.org" would succeed, yet remotely invoking hg would still fail.

FWIW, here is some SSH debug output

{{{
debug1: Reading configuration data /Users/loewis/.ssh/config
debug1: Applying options for *
debug1: Reading configuration data /etc/ssh_config
debug1: Applying options for *
debug1: Connecting to bitbucket.org [207.223.240.180] port 22.
debug1: Connection established.
debug1: identity file /Users/loewis/.ssh/identity type 2
debug1: identity file /Users/loewis/.ssh/id_rsa type -1
debug1: identity file /Users/loewis/.ssh/id_dsa type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.3
debug1: match: OpenSSH_5.3 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.2
debug1: Unspecified GSS failure. Minor code may provide more information
No credentials cache found

debug1: Unspecified GSS failure. Minor code may provide more information
No credentials cache found

debug1: Unspecified GSS failure. Minor code may provide more information

debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'bitbucket.org' is known and matches the RSA host key.
debug1: Found key in /Users/loewis/.ssh/known_hosts:53
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic
debug1: Next authentication method: gssapi-keyex
debug1: No valid Key exchange context
debug1: Next authentication method: gssapi-with-mic
debug1: Unspecified GSS failure. Minor code may provide more information
No credentials cache found

debug1: Unspecified GSS failure. Minor code may provide more information
No credentials cache found

debug1: Unspecified GSS failure. Minor code may provide more information

debug1: Next authentication method: publickey
debug1: Offering public key: /Users/loewis/.ssh/identity
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic
debug1: Trying private key: /Users/loewis/.ssh/id_rsa
debug1: Trying private key: /Users/loewis/.ssh/id_dsa
debug1: No more authentication methods to try.
Permission denied (publickey,gssapi-keyex,gssapi-with-mic).
}}}

~/.ssh/identity is the private key that should have worked.