Esse problema envolve duas máquinas. O que foi reinicializado? ssh-add adicionará apenas a chave no cliente. Se a chave não for aceita, não há um erro do cliente e um erro do servidor só será exibido se a opção -v for usada quando o ssh for chamado no cliente, para solicitar a conexão.
Suponho que é possível também que o Ubuntu tenha, por alguma razão desconhecida, alterado a mensagem de erro mostrada. Não é um erro emitido pelo servidor openSSH, como é usado no Debian (ou em qualquer outro lugar que eu tenha visto, por exemplo, RHEL, CentOS, Knoppix, outros).