It's all in how you attempt to access the hash keys...
$hash{0109} results in the illegal octal digit warning but $hash{'0109'} does not. And the following works fine.
#!/usr/bin/perl
use strict;
use warnings;
my %hash = map { chomp; split /,/ } <DATA>;
for (sort keys %hash) { print "$_ => $hash{$_}",$/; }
__DATA__
1001,choochoo
1002,candycane
1003,sockpuppet
1004,choochoo
1005,candycane
1006,sockpuppet6
1007,foo
1008,bar
0001,choochoo
0002,candycane
0003,sockpuppet
0109,choochoo
Update: Doh! I forgot to tell you why! You see Perl treats all numbers that start with a 0 as octal (unless the 0 is followed by an x in which case it is treated as hexadecimal).