I still don't get what the return value of the STORABLE_freeze function does to anything (other than returning an empty list to nullify the subroutine, I can't get the return value to do anything; maybe its broken?), but I've been messing with freeze/thaw hooks and here's what I have which may help (Maybe the secret is to just thaw it the way you want?):

#!/usr/local/bin/perl -l -w

use strict;
use Storable;
use Data::Dumper;

package MyPack;

sub new {
 my $class = shift;
 bless {attrib=>"red"}, $class;
}

sub STORABLE_freeze {
 my ($self, $cloning) = @_;
 return if $cloning;

 return $self;
}

# $self always seems to be an empty object
# blessed into the class, so lets re-bless it.
sub STORABLE_thaw {
 my ($self, $cloning) = @_;
 return if $cloning;

 bless $self, 'NoPackage';
 $self->{mykey} = "value";
 return $self;
}

package main;

my $obj = MyPack->new;
my $thing = { a=>"abc", b=>$obj };
print Dumper($thing);

store $thing, 'store.tmp';

my $another_thing = retrieve('store.tmp');
print Dumper($another_thing);

Output:
$VAR1 = {
          'a' => 'abc',
          'b' => bless( {
                          'attrib' => 'red'
                        }, 'MyPack' )
        };

$VAR1 = {
          'a' => 'abc',
          'b' => bless( {
                          'mykey' => 'value'
                        }, 'NoPackage' )
        };
[download]