A new release of Hash::MultiKey is out. The module has been completely rewritten. The current implementation uses the much superior approach Benjamin Goldberg suggested in a follow-up to the announcement of the initial release in comp.lang.perl.modules.
It's available here: http://search.cpan.org/author/FXN/Hash-MultiKey-0.02/ -- fxn