Tive o mesmo problema aqui e consegui resolver instalando o certificado digital com um setup que eu baixei do site da Valid.
Faça o download do arquivo no link a seguir: http://www.validcertificadora.com.br/upload/downloads/validcertificadora.exe
Clique na opção instalar e selecione o tipo de certificado A1, irá abrir um instalado, basta informar o tipo do cerificado, o local e senha do certificado que a instalação irá ser concluída. Após terminar tente enviar que deve funcionar.
O instalar .exe que é baixado no site da Valid não funcionou, diz que instalou o certificado mas não instala.
Aqui funcionou, espero que ajude vocês também.