This is sort of a Java problem, rather than an entirely Salesforce-specific problem, so depending on how you search for the answer, it could take you a while to get to why it failed, and what the actual solution is.
Basically: The Java used by Salesforce/Apex for SSL handshaking requires that the server certificate has a SAN (Subject Alternative Name) that matches the CN (Common Name) when the CN is an IP Address. This isn't an issue when the CN is a Hostname.
As such, as you can't use any of the (not particularly nice anyway) java workarounds for this issue; the solution to this involves generating a new server certificate with extra info on it. If you control the web service you're calling out to, that should be reasonably easy - otherwise you will need to get in touch with whoever administers the server and its certs and ask them to do this, as this is a definite blocker with no known workarounds in Salesforce (unless anyone else wants to chime in with one!).
Either way, someone will need to pay for a new Public CA signed server certificate to replace the old one. Depending on your Public CA, you will need to make sure you are buying a cert type that allows SANs, and be aware there may be extra charges per SAN added, depending on your provider.
To include the required SAN using Java 7's keytool, use the flag -ext san=ip:0.0.0.0 - filling in the appropriate IP address here, that matches the CN IP address, instead of 0.0.0.0.
To include the required SAN using openssl, include the following in your openssl.conf file used for generation
[req]
req_extensions = v3_req
[v3_req]
subjectAltName = @alt_names
[alt_names]
IP.1 = 0.0.0.0
Again, filling in the appropriate IP address that matches your CN, instead of 0.0.0.0
The Java flavoured Q&A can be found at https://stackoverflow.com/questions/8443081/
It turns out, as you said, that you can't have multiple certificates on the same IP address. Why every other browser and network service can handle this but Salesforce can't, I have no idea.
We were using a shared hosting provider, and once we got a dedicated IP address and put our sub-domain on that dedicated IP address, it worked.
Now, if only Salesforce would update it's error message to include the fact they don't work with wildcards or multiple certs on one IP address.
stony
Best Answer
Looks like your endpoint server has no valid certificate. Consider checking in browser.
Make sure that you are using valid certificate.