Since the same question was asked on stackoverflow too ... More details about the underlying problem can be found at my answer there (in short: a problem with OpenSSL known for years).
Comment on Re: LWP, "certificate verify failed" on known good certificate (paypal.com)