This appears to be around twice as fast with your sample data, and should be even faster for larger arrays:

sub fast_parasort (&@) {
    my($coderef, $master_array, @arrayrefs) = @_;

    my @indexes = sort { local ($a, $b) = ( $master_array->[$a], $mast
+er_array->[$b] ); &$coderef } ( 0 .. $#$master_array );

    map { [ @$_[ @indexes ] ] } ( $master_array, @arrayrefs );
}
[download]

The biggest distinction is that it avoids creating intermediate hashes and arrays -- instead, it just figures out the sorted order of the indices, based on your first array, and then uses slices to return the sorted version of all of the arrays.