ほい。これで OK のはず。

sub cat_sort ($$) {
my ($a, $b) = @_;
my $a_pri = $category_priorities{$a->label} || 1000;
my $b_pri = $category_priorities{$b->label} || 1000;
unless ($a_pri == 1000 && $b_pri == 1000) {
return $a_pri <=> $b_pri;
}
return $a_pri <=> $b_pri;
}

最後の return で返す値が間違えてたみたい。