In our case, everything WATCH OK, but it took most of the day to figure it out:
TL; DR: Check the certificate paths to make sure the root certificate is correct. In the case of COMODO certificates, it should say "USERTrust" and the "AddTrust External CA Root" should be released. NOT "COMODO" issued by "COMODO RSA Certification Authority".
In CloudFront docs: http://docs.aws.amazon.com/AmazonCloudFront/latest/DeveloperGuide/SecureConnections.html
If the source server returns an invalid certificate or a self-signed certificate, or if the source server returns the certificate chain in the wrong order, CloudFront removes the TCP connection, returns the HTTP error code 502, and sets the X-Cache header to Error from cloudfront.
We had the correct ciphers according to: http://docs.aws.amazon.com/AmazonCloudFront/latest/DeveloperGuide/RequestAndResponseBehaviorCustomOrigin.html#RequestCustomEncryption
Our certificate is valid according to Google, Firefox and ssl-checker: https://www.sslshopper.com/ssl-checker.html

However, the last certificate in the ssl verification chain was "CAODO RSA Domain Validation Secure Server CA" issued by the "COMODO RSA Certification Authority"
It seems that CloudFront does not have a certificate for the "COMODO RSA Certification Authority", and therefore believes that the certificate provided by the origin server is signed on its own.
This worked for a long time before it suddenly stopped. It so happened that I just updated our certificates for the year, but during the import something was changed in the path to the certificate for all previous certificates. They all started referring to the “COMODO RSA Certification Authority”, whereas before the chain was longer and the root was “AddTrust External CA Root”.

Because of this, switching to the old certificate did not fix the cloud problem.
I had to remove an additional certificate called "COMODO RSA Certification Authority", which did not refer to AddTrust. After that, all the certificate paths of my websites are updated to return to AddTrust / USERTrust again. A note can also open a bad root certificate from a path, click Details → Change Properties, and then disable it this way. This will immediately update the path. You may also need to delete several copies of the certificate found in the Personal and Trusted Root Certificate Authorities sections.

Finally, I had to re-select the certificate in IIS in order to get it to serve the new certificate chain.
After that, ssl-checker began to display the third certificate in the chain, which pointed to "AddTrust External CA Root"

Finally, CloudFront accepted the server of origin certificate and the provided chain as trusted. Our CDN started working correctly again!
To prevent this from happening in the future, we will need to export our newly created certificates from a machine with the correct certificate chain, i.e. do not trust or remove the certificate "COMODO RSA Certification Authroity" issued by "COMODO RSA Certification Authroity" (expiring in 2038). Apparently, this affects Windows machines where this certificate is installed by default.