Boa noite Rodrigo.
Aqui em SP, tive um verdadeiro incendio, pois todos os meus clientes emitiram nfe normalmente até umas 11 horas, e depois, todos tiveram as notas rejeitadas, ou mesmo verificação do serviço, com esta mensagem de erro.
Tentei de tudo, até desinstalar e reinstalar os pacotesa ACBR atualizados e nada.
Ai fui ao site da fazenda do meu estado, na aba de downloads, NFE, " https://www.fazenda.sp.gov.br/nfe/downl ... gentes.asp " e baixei os certificados. Quando descompactei, percebi que eram do mes de fevereiro/2012. então baixei os 3 certificados e o guia de instalação (pra não dar nada errado mesmo). Ai para minha surpresa, funcionou corretamente. Fiz acesso remoto aos clientes e repeti a instalação. Todos voltaram a funcionar. Espero que tenha ajudado, não só a vc, como a todos que ficaram como loucos tentando achar uma resposta. Abraço.