LWP refuses to connect via https

LWP refuses to connect via https

I am running the following perl snippet on Debian using Perl v5.14.2 and
libwww-perl v6.04-1
my $ua = LWP::UserAgent->new;
my $req = HTTP::Request->new("GET", "https://google.com/");
my $rep = $ua->request($req);
print $rep->status_line;
This instantly returns "500 Can't connect to google.com:443". I have tried
using LWP::Simple, Net::SSLeay, Crypt::SSLeay etc. without any success.
Oddly enough, executing the same code on an other Debian system running
exactly the same perl and LWP versions works.
So I thought, there is some error with the underlying system, but other
applications - like curl for any Browser - are working fine.
Also, openssl s_client -connect google.com:443 returns Verify return code:
20 (unable to get local issuer certificate) on both systems.
Has anyone ever encountered this phenomenon and has a solution? I am happy
to provide more information, if necessary. Thank you!
(I am not sure, whether this question is On-Topic on StackOverflow, as its
solution may relate to some Debian/OpenSSL configuration. If it does not,
please say so.)