Cloning with access key: Permission denied (publickey). fatal: Could not read from remote repository.

This is an intermittent bug that is happening to our customers (on Moss.sh).

Moss adds the site deploy key (using the current 1.0 API) to the user repository so that the server can clone it.

The access key always gets successfully added to the repository (it appears on the list of repository Access Keys), but sometimes the repository can't be cloned.
This is the output of the clone command:

#!bash

Cloning into '/home/user/sites/dev/repo'...
git@bitbucket.org: Permission denied (publickey).
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists. 

If we try to manually connect to bitbucket via SSH with that key then the output is the list of repositories that can be cloned with that key: (which is right)

#!bash

ssh -i priv.key bitbucket.org
PTY allocation request failed on channel 0
authenticated via a deploy key.


You can use git or hg to connect to Bitbucket. Shell access is disabled.

This deploy key has read access to the following repositories:

organization/repo: deploy-key-dev@server (Added by Moss) -- dev@server
Connection to bitbucket.org closed.

We suspect this could be related to an internal inconsistent state in Bitbucket, because in some cases if we add a new (and different) key to the same repository, the first key starts working (as it should).

Right now we don't have any specific example of a repository where this bug if happening, but this bug has been reported by some customers in the last days.