Os emissores de certificados geralmente têm mais de um certificado raiz.
O erro indica que seu certificado foi emitido por uma raiz que não é confiável pelos computadores que apresentam o erro. Isso se encaixa perfeitamente bem com o fato de que funciona em alguns clientes e outros reclamam disso. Não tem nada a ver com o fato de ser um certificado curinga.
Provavelmente isso não é problema seu; Se a pessoa que controla as estações de trabalho do cliente não atualizar a raiz de confiança ou remover o certificado da sua raiz de confiança ou tiver explicitamente desconfiado de um certificado na sua cadeia, você receberá erros de confiança. Esse é o problema deles para consertar. No entanto, você pode solicitar um novo certificado emitido por uma raiz diferente e esperar que a aceitação seja mais universal.