Thanks for checking that. You get the "INVALID_LOGIN" message?

I should have included versions:

Suggestions for the next step? Could you post output from your run, with the IO::Socket::SSL debugging turned on? I'm open to other ideas too, as I'm dangling off the edge of my expertise.

Yes, I do receive the "INVALID_LOGIN" response. Here is the full output with the debugging:

DEBUG: .../IO/Socket/SSL.pm:1545: new ctx 20310048
DEBUG: .../IO/Socket/SSL.pm:334: socket not yet connected
DEBUG: .../IO/Socket/SSL.pm:336: socket connected
DEBUG: .../IO/Socket/SSL.pm:349: ssl handshake not started
DEBUG: .../IO/Socket/SSL.pm:379: set socket to non-blocking to enforce
+ timeout=120
DEBUG: .../IO/Socket/SSL.pm:392: Net::SSLeay::connect -> -1
DEBUG: .../IO/Socket/SSL.pm:402: ssl handshake in progress
DEBUG: .../IO/Socket/SSL.pm:412: waiting for fd to become ready: SSL w
+ants a read first
DEBUG: .../IO/Socket/SSL.pm:432: socket ready, retrying connect
DEBUG: .../IO/Socket/SSL.pm:392: Net::SSLeay::connect -> -1
DEBUG: .../IO/Socket/SSL.pm:402: ssl handshake in progress
DEBUG: .../IO/Socket/SSL.pm:412: waiting for fd to become ready: SSL w
+ants a read first
DEBUG: .../IO/Socket/SSL.pm:432: socket ready, retrying connect
DEBUG: .../IO/Socket/SSL.pm:1533: ok=1 cert=21706288
DEBUG: .../IO/Socket/SSL.pm:1533: ok=1 cert=22023680
DEBUG: .../IO/Socket/SSL.pm:1533: ok=1 cert=22015040
DEBUG: .../IO/Socket/SSL.pm:1533: ok=1 cert=22007520
DEBUG: .../IO/Socket/SSL.pm:1148: scheme=www cert=22007520
DEBUG: .../IO/Socket/SSL.pm:1155: identity=login.salesforce.com cn=log
+in.salesforce.com alt=2 login.salesforce.com
DEBUG: .../IO/Socket/SSL.pm:392: Net::SSLeay::connect -> -1
DEBUG: .../IO/Socket/SSL.pm:402: ssl handshake in progress
DEBUG: .../IO/Socket/SSL.pm:412: waiting for fd to become ready: SSL w
+ants a read first
DEBUG: .../IO/Socket/SSL.pm:432: socket ready, retrying connect
DEBUG: .../IO/Socket/SSL.pm:392: Net::SSLeay::connect -> 1
DEBUG: .../IO/Socket/SSL.pm:447: ssl handshake done
DEBUG: .../IO/Socket/SSL.pm:1582: free ctx 20310048 open=20310048
DEBUG: .../IO/Socket/SSL.pm:1587: free ctx 20310048 callback
DEBUG: .../IO/Socket/SSL.pm:1590: OK free ctx 20310048
500 Server Error
<?xml version="1.0" encoding="UTF-8"?><soapenv:Envelope xmlns:soapenv=
+"http://schemas.xmlsoap.org/soap/envelope/" xmlns:sf="urn:fault.partn
+er.soap.sforce.com" xmlns:xsi="http://www.w3.org/2001/XMLSchema-insta
+nce"><soapenv:Body><soapenv:Fault><faultcode>INVALID_LOGIN</faultcode
+><faultstring>INVALID_LOGIN: Invalid username, password, security tok
+en; or user locked out.</faultstring><detail><sf:LoginFault xsi:type=
+"sf:LoginFault"><sf:exceptionCode>INVALID_LOGIN</sf:exceptionCode><sf
+:exceptionMessage>Invalid username, password, security token; or user
+ locked out.</sf:exceptionMessage></sf:LoginFault></detail></soapenv:
+Fault></soapenv:Body></soapenv:Envelope>
[download]

This was run with perl v5.14.3 on 64-bit Linux. Since the cert verification will either pass or fail regardless of the payload, you could try an even simpler script such as this:

use strict;
use warnings;

use LWP::UserAgent;
use Mozilla::CA;
my $ua = LWP::UserAgent->new(
        ssl_opts => {
                verify_hostname => 1,
                SSL_ca_file => Mozilla::CA::SSL_ca_file()
        }) or die;
my $url = $ARGV[0] || 'https://login.salesforce.com/';
my $res = $ua->get($url);
print $res->code . "\n";

exit;
[download]

You can then run this with any number of known, good URLs (eg: https://www.google.com/ or https://metacpan.org/ ) to see if any of them pass verification.

Good luck.

> Mozilla::CA is 20141217

And that's where your problem is. Mozilla removed lots of 1024-bit root-CA and the CA you need is among these. If you use an older version of the CA store (like from 2013) it works again.