This has nothing to do with why your test(s) are failing... but while looking into the code to figure out if you're really depending on Crypt::Rijndael (or if that require Crypt::Rijndael was maybe just a misguided attempt to load the module only if available (which wouldn't work... but doesn't seem to be the case here)), I incidentally noticed that you might simplify your hex <--> bin conversions

sub yubikey_hex2bin
{
        my $in = $_[0];
        my $out = "";
        for(my $k=0;$k<length($in);$k+=2)
        {
                $out .= chr(hex(substr($in,$k,2)));
        }
        return $out;
}

sub yubikey_bin2hex
{
        my $in = $_[0];
        my $out = "";
        for(my $k=0;$k<length($in);$k++)
        {
                $out .= sprintf("%2x",ord(substr($in,$k,1)));
        }
        $out =~ s/ /0/g;        # this is a hack.. not sure why it has
+ to be like this...
        return $out;
}
[download]

by using the Perl builtins un/pack with the "H" template, i.e.

# hex2bin
$bin = pack   "H*", $hex;

# bin2hex
$hex = unpack "H*", $bin;
[download]

Or, if you wanted to stick with your conversion routines, you could get rid of the $out =~ s/ /0/g hack by using "%02x" in sprintf().

Yeah, I know you didn't ask for a code review, so my apologies, if this advice is unsolicited... :)