The name verification is guided by RFC 2818 Section 3.1, more specifically on wildcards:
Matching is performed using the matching rules specified by
[RFC2459]. If more than one identity of a given type is present in
the certificate (e.g., more than one dNSName name, a match in any one
of the set is considered acceptable.) Names may contain the wildcard
character * which is considered to match any single domain name
component or component fragment. E.g., *.a.com matches foo.a.com but
not bar.foo.a.com. f*.com matches foo.com but not bar.com.
Here the "domain name components" a separated by the dots, and do not include them.
This is also clarified in RFC 6125 (which also discourages the use of wildcard certificates, but that's a different problem).
Instead of putting your host name in the Common Name RDN of the Subject DN, you could have two Subject Alternative Name entries in the same certificate: one for *.example.com and one for example.com. The CN is only meant to be a fallback solution anyway:
If a subjectAltName extension of type dNSName is present, that MUST
be used as the identity. Otherwise, the (most specific) Common Name
field in the Subject field of the certificate MUST be used. Although
the use of the Common Name is existing practice, it is deprecated and
Certification Authorities are encouraged to use the dNSName instead.
example.comis pointing to the correct server that has your certificate? If you are using Google's naked domain redirect for example, it will show the message you describe.