Tudo se baseia em uma Cadeia de Confiança, onde os Certificados Raiz, são amplamente conhecidos, salvos e considerados como Seguros, pelo Sistema Operacional...
Quando o Servidor (SEFAZ) muda de Certificado... Pode ocorrer, do Client (máquina do seu cliente), ainda não conhecer as Autoridades Certificadoras, que geraram o novo certificado da SEFAZ...
Se o Certificado Raiz que o Servidor está usando, não for conhecido pela máquina do seu cliente, ele pode rejeitar a conexão (e vice versa)
Em alguns casos, atualizar a cadeia de certificados Raiz, pode até ser feita pelo próprio Windows, em processos de atualização do S.O.