You can't use each(%foo) to process a hash in sorted order.

my %type_bands_rating_HoH = (
    "Rock Bands" => {
                      "Smashing Pumpkins" => "5 stars",
                      "Aerosmith"         => "5 stars",
                      "Foo Fighters"      => "5 stars",
    },
    "Pop Bands"  => {
                      "Duran Duran"       => "5 stars",
                      "Blondie"           => "5 stars",
    },
);

foreach my $type ( sort keys %type_bands_rating_HoH ) { 
    my $band_rating_href =   $type_bands_rating_HoH{$type};

    print "KEY: $type \n";

    foreach my $band ( sort keys %{ $band_rating_href } ) { 
        my $rating = $band_rating_href->{$band};
        print "nested key: $band, rating $rating\n";
    }

    print "-------\n";
}
[download]