You're only printing the top level array which is never shuffled. If you were to use Data::Dumper or Data::Denter to print your data structures, you would see that the second-level arrays are indeed shuffled.

It might be worth making the shuffler into a function:

sub shuffle
{
    my $array_ref = shift;
    for ( my $i = @$array_ref; --$i; )
    {
        my $r = int rand ( $i + 1 );
        @$array_ref[ $i, $r ] = @$array_ref[ $r, $i ];
    }
}
[download]

This will let you recurse through an array of arrays:

sub recursive_shuffle
{
    my $array_ref = shift;
    for my $element ( @$array_ref )
    {
        recursive_shuffle( $sub_array ) if ref $element eq 'ARRAY';
    }
    shuffle( $sub_array );
}
[download]

(This code is untested.)