Depende de qual aplicativo cliente está gerando os avisos. É um navegador da web? Em caso afirmativo, qual navegador?
Para o Internet Explorer, adicione o certificado (apenas a chave pública) ao armazenamento de certificados Raiz Confiável do usuário ou do computador. As instruções exatas para fazer isso variam um pouco dependendo da versão do Windows em que o cliente está sendo executado.
O Firefox não usa o armazenamento de certificados do Windows, então você deve adicioná-lo à própria loja do Firefox. Em 3.6, isso pode ser encontrado em Ferramentas - Opções - Avançado - Criptografia. Clique no botão Visualizar certificados e adicione-o à lista Autoridades ou Servidores .
Não tenho certeza sobre o Chrome, o Opera ou o Safari.