Descobri que nenhum dos usuários tinha uma identidade, apesar de a chave do agente ser encaminhada.
Verifique na máquina local usando:
ssh-add -L
Se você ver: O agente não tem identidades.
Você também pode precisar digitar:
ssh-add
Isso resolveu nosso problema. Espero que ajude alguém.
Em um caso, o usuário tinha uma identidade local, mas não era a chave que ele estava usando, mas uma chave alternativa usada em um ambiente diferente. Como ele poderia agir como esperado nesse ambiente, isso nos deu a impressão de que o problema estava no servidor. Para adicionar uma identidade específica, usamos
ssh-add ~/.ssh/his-alternate-keyfile