Try running the following snippet of code having modified the use lib ...; statement to match that you are using in your program.

#! perl -slw
no warnings;
use lib 'whatever you are using';
use Storable;

for ( sort keys %INC ) {
    printf "%20s => %s ", $_, $INC{ $_ };
    s[/][::]g;
    s[.pm][];
    print eval "\$$_\::VERSION";
}
[download]

The output should look something like that below and will allow you to identify where the version of Storable is being picked up from and which version it is.

P:\test>used
       AutoLoader.pm => c:/Perl/lib/AutoLoader.pm 5.60
             Carp.pm => c:/Perl/lib/Carp.pm 1.02
           Config.pm => c:/Perl/lib/Config.pm
       DynaLoader.pm => c:/Perl/lib/DynaLoader.pm 1.05
         Exporter.pm => c:/Perl/lib/Exporter.pm 5.58
   Exporter/Heavy.pm => c:/Perl/lib/Exporter/Heavy.pm 5.58
            Fcntl.pm => c:/Perl/lib/Fcntl.pm 1.05
         Storable.pm => c:/Perl/lib/Storable.pm 2.12
         XSLoader.pm => c:/Perl/lib/XSLoader.pm 0.02
c:/Perl/lib/auto/Storable/autosplit.ix => c:/Perl/lib/auto/Storable/au
+tosplit.ix
           strict.pm => c:/Perl/lib/strict.pm 1.03
             vars.pm => c:/Perl/lib/vars.pm 1.01
         warnings.pm => c:/Perl/lib/warnings.pm 1.03
warnings/register.pm => c:/Perl/lib/warnings/register.pm 1.00
[download]

Did you create the frozen data and then upgrade Storable? Because if not, something is seriously wrong with your install.