Try upping your paranoia level slightly, see if that gives you more enlightening errors?

my $rsa = new Crypt::RSA ();
unless (ref $rsa) { die "Not a reference: $rsa"; }
unless ($rsa->isa('Crypt::RSA') { die "Not a Crypt::RSA: $rsa"; }
my $checksum;
{ # scope for temp var
  my $decrypt = $rsa->can('decrypt');
  unless (ref $decrypt) { die "Not a reference: $decrypt"; }
  unless (ref $decrypt eq 'CODE') { die "Not a coderef: $decrypt"; }
  $checksum = $decrypt->(Cypertext => $encrypted,
                         Key       => $public_key,
                         Armour    => 1,
                        ) or die "Can't decrypt: " . $rsa->errstr();
}
unless ($checksum) { die "No checksum after decrypt"; }
[download]

At least this may pinpoint the problem more precisely...?