It verified for me by passing trial division:

#!/usr/bin/perl -l

use strict 'refs';
use warnings FATAL => 'syntax';
use Crypt::RSA::Key;
use Crypt::RSA::Key::Public;
use Crypt::RSA::Key::Private;
use Crypt::RSA::SS::PSS;
use Math::Pari qw(PARI);

my ($message, $rsa, $pss, $signature, $verify);
my ($public, $private);

$message = "hello";

$rsa = new Crypt::RSA::Key;
($public, $private) = 
    $rsa->generate( 
        Size      => 1024,
        Verbosity => 2,
        Filename  => "key",
    ) or die $rsa->errstr();

$pss = new Crypt::RSA::SS::PSS;
$signature  = $pss->sign( 
    Message => $message,
    Key     => $private, 
) || die $pss->errstr;

$verify = $pss->verify( 
    Message   => $message,
    Key       => $public,
    Signature => $signature,
) || die $pss->errstr;

my $i = 0;
foreach $verify(1 .. 10) {
    print $verify ? "ok" : "not ok";
    print " ", ++$i;
    sleep 1;
}

my $key = new Crypt::RSA::Key::Public(
    Filename => "key.public",
);
$signature = pack("H*", '03808458..73E92');

foreach $verify(1 .. 10) {
    print $key ? "ok" : "not ok";
    print " ", ++$i;
    sleep 1;
}
[download]