[Don't upvote this - Chris' answer is far better! I wouldn't have written this had I seen his. I'm leaving it here for folks who need an (over-)simplified explanation of why this happens, so they can better implement Chris' solution.]
This error generally indicates an issue with the SSL certificate bundle on your end and/or the mail server's end.
Without getting deep into how SSL certificate authorities work (Wikipedia has a much better explanation than I can provide): There's a handful of "root" certificate authority (CA) companies. Symantec, GoDaddy, Comodo, also many governments/militaries. Every SSL certificate is either:
- a root certificate owned by a root CA;
- "signed" (cryptographically verified as legit) by someone who has a root certificate;
- signed by someone who's got a signed certificate themselves. In this case, you have a root cert, one or more intermediate certs, and the cert on (in this case) the mail server;
- A cert that can't trace its lineage back to a root cert. These are known as "self-signed" certs. Your data is encrypted - but you can't guarantee the person on the other end is who they claim.
The problem here is, "Who gets to call themselves a root cert? And how do we know that the intermediate certs have been signed by a root cert?"
The answer to "who is a root cert?" is determined by whatever software you're using. Every web browser includes all the root certs they recognize in their installer. Each web browser company has their own (intense) process. E.g. here's the list Firefox currently uses. This list changes all the time!
So that leads to two more situations:
- The mail server's cert can trace its lineage back to a newer root CA, but one that your older software can't recognize because it didn't ship with the newer root cert.
- The mail server's cert was signed by a legit intermediate cert, but is failing to tell your CiviCRM about it (incomplete "certificate chain").
Your web server has a stack of root certs installed - PHP uses the ones provided by OpenSSL. Chances are, you update OpenSSL a lot less frequently than your web browser!
So most likely, your web situation is the fifth one - your openSSL is too old. If you're running Linux, update to the latest version of your distribution.
It's also possible that your situation is the sixth one - in which case you need to tell the mail administrator to fix their certificate chain.
Chris gives much better answers on how to figure out which of these is true!