I realize this is an ancient thread, but I ran across the same error and finally figured out the problem.
After de-serializing the private key (I just used the Crypt::RSA::Key::Private->read method) you MUST use the 'reveal' method and give it the password you originally used to generate the keypair.
my $rsa_private = new Crypt::RSA::Key::Private;
my $private = $rsa_private->read(Filename => "id_rsa");
## This is vital if you want the loaded private key to work.
$private->reveal(Password => "originalkeypairpassword");