Figura 01 - Certificado Inválido
Solução Rápida- Remova todos os certificados;
- Faça o download InstaladorCadeias_1.0.2.0.exe e instale como administrador;
- Teste novamente.
Solução Detalhada
01 -Vá em pesquisar e digite "executar" ou utilize o comando (windows + R), digite, certlm.msc, para abrir a interface de certificados, caso esse comando não funcione, digite certmgr.msc;
02 - Abra a pasta Autoridades de Certificações Raiz Confiáveis e selecione a opção Certificados, remova todos os certificados, 
clicando neles e pressionando a tecla delete um a um;
Figura 02 - Certificados
03 - Após deletar todos os certificados, aperte a tecla F5 para atualizar a página, e remova qualquer novo certificado que aparecer, repita esse processo algumas vezes, até que retorne sempre vazio;
04 - Faça o download do arquivo InstaladorCadeias_1.0.2.0.exe e salve em uma pasta de sua preferência;
05 - Através do botão direito do mouse 
selecione a opção Executar como administrador;
06 - Clique em 
, e prossiga até que o processo seja finalizado;
Figura 03 - Instalador de Cadeias
07 - Teste novamente a comunicação com a SEFAZ;
Caso ainda não funcione, vá em opções da internet, na aba avançadas, na seção segurança e desabilite as configurações:
- Avisar quando houver incompatibilidade de endereços de certificado;
- Verificar revogação de certificados do servidor;
- Verificar se há certificados revogados do fornecedor.
Figura 04 - Propriedades de Internet
08 - Salve, reinicie a máquina, e teste novamente.