I recently upgraded a server, Perl modules included, and went through a similar problem. Scripts that were there for ages suddenly failed with a message like yours. I solved my problem by including the header key in the call to new with the value 'randomiv'.

my $cipher = Crypt::CBC->new( -key   => $key,
                             -cipher => 'Blowfish',
                             -header => 'randomiv',
                             -salt   => 1,
                           );
[download]