Zhris,
If I had to do this, I would probably use a Schwartzian Transform. First, the explanation: Prepend each color with a 1 character value depending on if it is above 0 or not. Then, perform a normal ASCIIbetical sort on the list. Finally, remove the leading character. *Untested*

my @list = 
    map {substr($_, 1)}
    sort
    map {$lookup{$_}{val} > 0 ? "A$_" : "B$_"} @list;
[download]

Update: You asked if this could be done without breaking out of a sort block because you would be choosing the block from a hash. You could just as easily use a subroutine instead of a sort block but you could do the same trick in the block itself:

sort {
    my $lhs = $lookup{$a}{val} > 0 ? "A$a" : "B$a";
    my $rhs = $lookup{$b}{val} > 0 ? "A$b" : "B$b";
    $lhs cmp $rhs
}
[download]