Bem, a caixa de diálogo informa exatamente o que está errado - seu computador não confia no certificado que está sendo apresentado.
O motivo pelo qual seu computador não confia no certificado pode estar relacionado ao seu antigo Controlador de Domínio, mas talvez não. Eu suspeito que seu antigo controlador de domínio estava hospedando serviços de certificados e era uma autoridade de certificação confiável para sua empresa e emitiu um certificado para serviços do Exchange e, quando você removeu o DC antigo, removeu um certificado raiz ou intermediário no processo.
Você precisa examinar o certificado sendo apresentado e ver em que parte da cadeia está quebrada a confiança. Como eu disse, suspeito que um certificado intermediário ou raiz ausente foi emitido pela sua Autoridade de Certificação antiga no Controlador de Domínio que você removeu.
Se for esse o caso, você pode instalar a função Serviços de Certificados do Active Directory em seu novo Controlador de Domínio e criar uma nova autoridade de certificação para substituir a antiga. Em seguida, execute o assistente de certificado do Exchange e gere um CSR para o seu servidor Exchange. Entregue isso à sua autoridade de certificação no seu controlador de domínio, emita um certificado, importe-o para o Exchange e atribua-o aos serviços do Exchange.
Alternativamente, gaste algumas centenas de libras e obtenha um certificado assinado por uma autoridade confiável como a DigiCert e você não terá que se preocupar com o incômodo de gerenciar sua própria Autoridade de Certificação. O bônus adicional dessa opção é que, se você tiver dispositivos móveis usando o ActiveSync, eles não precisarão importar seu certificado porque o certificado do DigiCert (ou de quem você escolher) provavelmente já estará instalado no dispositivo.