I'm using a UCC certificate (i.e. CN=host.domain.name). I wonder whether wildcard may be unsupported, and whether a self-signed certificate might need the FQDN (or IP address) to be included in the CN or SAN fields.
In either case, capturing the TLS negotiation will show the failure reason via the Alert codes, either the server rejecting the client, or the client rejecting the server.
You could also use the openssl toolkit to help troubleshoot TLS server problems, see command "openssl s_client -connect paloaltohost.domain.com:443".