I've run into this a few times and it was due to a certificate chain being incomplete. If you are using the standard java trust store, it may not have a certificate that is needed to complete the certificate chain which is required to validate the certificate of the SSL site you are connecting to.
I ran into this problem with some DigiCert certificates and had to manually add the intermediary cert myself.