Aqui está a maneira que eu sempre recomendo instalar certificados auto-assinados para coisas como esta:
Na máquina do cliente: Vá para Iniciar > Executar ... (se o Windows 7, Win + R) > digite 'mmc' e pressione Enter. Quando o MMC aparecer, File > Adicionar / Remover Snap In ... e escolha o snap-in 'Certificados'. Ele vai pedir para o usuário, computador, etc ... escolher o computador local. Quando o snap-in for carregado, escolha a pasta Raiz Confiável, clique com o botão direito dentro da lista de certificados e escolha Tarefas > Importar ... e ESPECIFICAR que o certificado seja importado para a pasta Raiz Confiável. Não deixe que decida onde colocá-lo. Funciona bem para mim.
Se ainda assim não funcionar, pode ser necessário baixar e importar toda a cadeia de certificados de sua autoridade de certificação interna.