Try using HTTP with the sandbox server.
change https://www.sandbox.paypal.com/cgi-bin/webscr to http://www.sandbox.paypal.com/cgi-bin/webscr
Update: and this my $ua = LWP::UserAgent->new(ssl_opts => { verify_hostname => 1 }); to this my $ua = LWP::UserAgent->new;
That would mean your SSL encryption was not right or PP could have sent it to you none HTTPS or the sandbox server does not run SSL or...