While I don't have much in the way of implementation suggestions, I do have a few requirements that I'd like to see from a switch statement. You may already implement some of these - I haven't checked.

• Ordering of cases. This is very important with fall-through, because I may only want fall-through to a specific location. So, something like:

  switch (i) {
      0,1: foo();
      2: bar(); break;
      3: baz(); break;
  };
  [download]

  0 and 1 must fall through to 2, but not 3. It also matters with the case of regex matches (q.v. below).
• Smart matching. If I give you '5' as a case, I want '05' to match it. If I give you qr/^boo.*boo$/, I want you to match 'booboo' and 'booBOOboo'. If I give you a code reference, I want you to pass the value to the coderef which will return true or false. And, so forth.
• Options for how matching happens. I might want a switch statement to be case-sensitive or case-insensitive. I might want matches to always be string-matches (in which case '5' and '05' are different) or I might want them to be smart.
• I want a redo statement in my switch. This is actually very useful in parsing, particularly something like CSV data. Text::xSV basically implements a switch statement with redo as its parsing engine. (Oh, and the cases are primarily regexes.)

Taking a page from Class::MakeMethods, it might be useful to have each case be an arrayref. The last value is the action to take. All others are the case options. If the first value begins with '--', then it's an optional modifier to how to handle the next case option. So, maybe something like:

my $switch = Switch->new(
    [ '5', sub {} ], # Matches '005'
    [ '--string-match', '6', sub {} ], # Doesn't match '006',
    [ qr/floober/, sub {} ] # regex match
    [ sub { $foo->bar( @_ ) }, sub {} ] # coderef
    [ 1 .. 3, 8 .. 20, sub {} ] # Multiple cases
);
[download]

That would be a useful module.