I strictly followed all the steps described on page https://www.cloudera.com/documentation/enterprise/latest/topics/cm_sg_create_deploy_certs.html
The only thing I had to do differently is to use root certificate instead of intermediate ones since I do not have those.
"This error is a fairly generic one but it often relates to a few different things. The certificate presented by the server is not trusted because the CA chain cannot be established, the root certificate is not available, or the certificate presented is expired."
How to diagnose which of those reasons created a problem?
One thing I do not understand is how agents authenticate to CM. Should not truststore on CM, in addition to root cert contain agent certs? The instructions only say import root cert into the truststore. Should not truststores on agent machines contain CM server certificate? I would import all public agent and server certificates into the truststore and distribute it on all the machines.
That is a harder question to answer. Generally speaking in cases like this you should step through each section to ensure that everything is correct. If you are trying to setup Level 3 TLS for example you must make sure that the certificate have the following two OIDs.
When you use a root CA it is the signing authority for these certificates. Because it is the signing authority if you trust that authority it can be used to validate the certificates it has issued. This is the basic concept behind TLS certificate trust.