Surely you meant DBM::Deep->new( './test.dbm' );. Note the arrow operator, not a double colon :)

There is info in the docs about autovivification (update: The proper documentation segment). Try doing this instead and see if it works:

$db->{test} = {};
$db->{test}->{fred} = [ 1 .. 10 ];
$db->{test}->{bill} = [ 'a' .. 'z' ];

# if the above doesn't work either, try the
# following ridiculous snippet:
$db->{test} = {};
$db->{test}->{fred} = [];
push( @{ $db->{test}->{fred} }, $_ ) for ( 1 .. 10 );
$db->{test}->{bill} = [];
push( @{ $db->{test}->{bill} }, $_ ) for ( 'a' .. 'z' );
[download]

update: It's your command line switches. 'l', the line ending one is making this happen somehow. I tried mucking around with your script and as soon as the '-l' switch is removed it's all fine. Final working script:

#!c:/perl/bin/perl -w
use strict;

use DBM::Deep;
use Data::Dumper;

unlink './test.dbm';

my $db = DBM::Deep->new( './test.dbm' );  
$db->{test} = { fred => [ 1 .. 10 ], bill => [ 'a' .. 'z' ] };

print Dumper $db;
[download]