[niteriderxp]

The proper way to self-sign a certificate is to install a Certificate Authority (CA) on your server.
Then one generates a certificate request using Exchange and submits it to the Certificate Authority.
The CA then signs the certificate with its private key and it is installed on the Exchange server.
The CA's certificate (containing only its public key) is then installed on each client device.
The device verifies the validity of the Exchange certificate utilizing the CA's certificate.

Unfortunately, I am not sure what could be causing your problem.