CloudFront distribution and AWS issued certificate gives SSL_ERROR_NO_CYPHER_OVERLAP

So, in my update, I mentioned adding CNAMEs from a blog post. This was it, the second I did that, it started working.

To clarify, I did this to solve my problem:

1. Edit your CloudFront distribution.
2. Under the tab General, click edit.
3. In the Alternate Domain Names text box, add (at least) the something.mydomain.com that you have configured to this distribution's endpoint/URL in Route53.
4. Save your changes.

This solved it instantly for me, but remember that CloudFront configuration changes sometimes can take some time to be pushed out.

As stated by OP in an edit error caused when a CNAME entry for the apex (naked) domain, www subdomain, other subdomain or other domain(s) are not listed in the distribution.

To fix add at least one CNAME to the distribution in CloudFront.