The problem is actually in the constructor, specifically in the line _title => $args{title} || die "Sorry, we need a title for this menu!". I believe that perl is parsing this such that the remainder of the hash population is read as parameters to the die statement (recall that die can take a list). Try removing the die statement and you'll get the behavior you want. (Update I just grokked dpuu's comment before. Same point). More generally, it's a good idea to separate data validation from the population of data structures precisely to avoid wierd bugs like this one.

Some other comments:

1. first of all, for an initial attempt at module writing, this is readable and fairly sophisticated, so kudos.
2. Secondly, in your constructor, it would make more sense to change $self to $class, as the first element of @_ in a class method is the name of the package, not a reference to an instance (with the exception of constructors that double as clone methods, as discussed in perl oo)
3. Next, I would standardize your argument passing conventions since at present you're passing both hashes (set_choices) and named lists (new).
4. Finally, in set_choices, since it's getting complex, assign $_ to an intelligible temporary variable. Tracking its value in anything other than simple loops, maps, etc., can get hairy.