A 'Schwartzian Transform' is worth trying:

sub do_msalist {
    my (%country, %state, %msaname, @msakeys);
     ...
    my @sorted = map  { $$_[0] }
                 sort { $$a[1] cmp $$b[1] }
                 map  { [$_, americentric_key(
                             $country{$_},
                             $state{$_},
                             $msaname{$_},
                             $_
                 )]} @msakeys;
    for (@sorted) {
     ...
    }
}

sub americentric_key {
 # This part may need adjusting depending on your data
 sprintf("%10s%10s%10s%10d", @_;
}
[download]