O problema no meu caso foi que o algoritmo de assinatura do certificado em particular era sha256rsa. Em KB2763674 , está documentado que com hashes de certificado de 256 bits ou mais, um programa assinado pode falhar para iniciar no Windows Vista SP2 ou no Windows Server 2008 SP2. Instalando o KB-patch e reinicializando, resolveu o problema.