Yes, I provided the latest Mozilla Certificate Authority file. My Mac laptop does not have the Mozilla::CA package loaded, so I just provided the file (version 20160420) in the directory I was running the perl program in. If I don't provide the file, the connection fails by not being able to verify the server. The server that I need to get this working on does have Mozilla::CA (version 20120309), so I won't use that line either. My perl version is 5.18.2.

I believe I am successfully verifying the server certificate.

Can you dump out all the SSL options on your successful connection?

The only option is the one you've set.

$ cat 1166599.pl 
#!/usr/bin/perl
use strict;
use warnings;
use LWP::UserAgent;

my $ua = LWP::UserAgent->new();
$ua->ssl_opts(verify_hostname => 1);
my $host = 'https://tlstest.paypal.com';
my $req = HTTP::Request->new(GET => "$host");
my $res = $ua->get($host);
if (not $res->is_success) {
  print $res->as_string . "\n";
} else {
  print "Success\n";
  print $res->decoded_content . "\n";
  foreach ($ua->ssl_opts) { print "$_ => " . $ua->ssl_opts($_) . "\n";
+ }
}
palma pete 2309 $ ./1166599.pl 
Success
PayPal_Connection_OK
verify_hostname => 1
$ perl -v

This is perl 5, version 20, subversion 3 (v5.20.3) built for x86_64-li
+nux-thread-multi
(with 16 registered patches, see perl -V for more detail)

Copyright 1987-2015, Larry Wall

Perl may be copied only under the terms of either the Artistic License
+ or the
GNU General Public License, which may be found in the Perl 5 source ki
+t.

Complete documentation for Perl, including FAQ lists, should be found 
+on
this system using "man perl" or "perldoc perl".  If you have access to
+ the
Internet, point your browser at http://www.perl.org/, the Perl Home Pa
+ge.
[download]

The options look the same. This must be a version issue. Below are my versions of perl and involved modules. The IO modules look out of date.

Perl             5.18.2
LWP::UserAgent   6.05
LWP::Protocol    6.00
IO::Socket       1.36
IO::Socket::SSL  1.966
[download]

How do these compare with your working set?