For starters, you're using parentheses instead of curlies to create your inner hashes (within the SUBMENU keys). This means the data structure you think you have isn't the data structure you actually created. Try passing %menus through Data::Dumper (this is a great module that I find is invaluable for debugging).

Secondly, the print_main_menu and print_sub_menu functions are very similar. I'd suggest refactoring them into a single, more generalized sub that takes a hash reference as a parameter. Tweaking your code slightly gives this:

sub print_menu 
{
    my ( $href ) = @_;
    print "$_\t", $href->{$_}, "\n"
        for ( sort keys %{ $href } );
}
[download]

There are additional errors, also. For example, I don't think you really wanted $menu->{$_} (in print_main_menu), unless you have a hash ref assigned to $menu somewhere that isn't shown in this example. I suspect you meant to refer to %menus, which is not a reference so the keys would be accessed by $menus{$_}.

Finally, since it wasn't obvious in your example, use strict and warnings! :-)