This was my take on the problem:

#!/usr/bin/perl
use warnings;
use strict;

my %hash = ();
my %value_hash = ();

while(<DATA>) {
    chomp;
    my ($first_key, $second_key, $value ) = split /\s+/;
    $hash{$first_key}{$second_key} = $value;
}
#
# Map the hash of a hash of a value into a 
# hash of the value containing an array of key pairs.
# Then sort on the new hash. 
#
for my $colour ( sort keys %hash ) {
    for my $device ( sort keys %{$hash{$colour}} ) {
        my $val = $hash{$colour}{$device};
        printf "%-15s %-15s %5d\n", 
            $colour, $device, $val;
        push @{$value_hash{ $val }} , [ $colour, $device ];
    }
}
print "\n\nSorted Result:\n\n";
for my $val ( sort { $b <=> $a } keys %value_hash ) {
    for my $key_pair ( @{$value_hash{$val}} ) {
        printf "%-15s %-15s %5d\n", 
            @$key_pair[0], @$key_pair[1], $val;    
    }        
}
__DATA__
red           bike             5
red           car              4
red           shoes            20
yellow        shoes            1
yellow        skates           1000
[download]

And the output is:

C:\Code>perl multi_hash_sort.pl
red             bike                5
red             car                 4
red             shoes              20
yellow          shoes               1
yellow          skates           1000


Sorted Result:

yellow          skates           1000
red             shoes              20
red             bike                5
red             car                 4
yellow          shoes               1
[download]