So I'm going to reply to this (after an appropriately long delay :-), because I just upgraded to wheezy and am having the same problem and search turned this up.

I really hate bashing %ENV to communicate between different parts of Perl. As a general rule of thumb, if you're trying to communicate intra-process, there's nearly always a better way than messing with %ENV.

Also it looks like IO::Socket::SSL is preferred over Net::SSL/Crypt::SSLeay these days. In my original version of this post there was some question of whether the latter is even being maintained and can actually do certificate verification, but apparently it is and can. I got confused because Crypt::SSLeay evidently can't do hostname verification which is a distinct issue (though arguably still an issue). There's also a comment in the Crypt::SSLeay pod to the effect that that module only exists to https-enable LWP::UserAgent whereas IO::Socket::SSL is a more general-purpose package.

I could be wrong about all this, but in any case if you want to be able to explicitly control what you're using, which, unfortunately, you have to in order to be able to specify SSL options to LWP::UserAgent, here's my code:

# Make sure LWP::UserAgent uses the right kind of socket
use IO::Socket::SSL;
$NET::HTTPS::SSL_SOCKET_CLASS = 'IO::Socket::SSL';
use LWP::UserAgent;

# some servers immediately go radio-silent
# if you try SSL versions < 3
our %ssl_options = (SSL_version => 'SSLv3');

...
$ua = LWP::UserAgent->new(ssl_opts => \%ssl_options),
[download]

((Update (11/5/2014): leave SSL_version alone; see comment below))

The NET::HTTPS line is for the case where LWP::UserAgent has already been loaded, already chose the wrong default socket implementation because of what was in place when LWP::UserAgent was loaded the first time, and you need to undo that.

I suppose if you badly need to play nice with other packages that explicitly depend on Net::SSL being used, there's also

{
  local $NET::HTTPS::SSL_SOCKET_CLASS = 'IO::Socket::SSL';
  $ua = LWP::UserAgent->new(ssl_opts => \%ssl_options),
}
[download]

Thank you very much. That was my problem. Forcing to v3 worked.

And now of course, because of the POODLE bug, the latest version of IO:Socket::SSL has version 3 completely disabled. So the above fix is no longer the Right Thing.

It also seems that IO::Socket::SSL now deals better with sites that immediately close or drop connections for bad SSL versions, so it's no longer necessary to force a specific version (which is good, since this is evidently going to be constantly changing anyway). So my code now reads

our %ssl_options = ();
[download]