Acho que sei o que é. Há algum tempo foi descoberta uma falha grave no OpenSSL (base do SSH), todos os certificados que foram gerados no período da falha foram invalidados.
Se vc se conectou a esse servidor antes da falha, agora vc tem anotado no gerenciador esse certificado, mas ele foi invalidado e substituído. Vc tem que, de alguma forma, fazer o nautilus esquecer esse certificado antigo e aprender o novo.