It's not the fault of tied hashes.

use Tie::Hash qw( );
our @ISA = 'Tie::StdHash';

sub STORE {
   my ($self, $key, $val) = @_;
   print($key eq "\x{05D0}" ? "utf" : "not utf", "\n");
   return $self->SUPER::STORE($key, $val);
}

my %h;
tie %h, __PACKAGE__;
$h{"\x{05D0}"} = 1;   # Prints 'utf' in 5.8.6
[download]

dbm probably doesn't support unicode keys. The workaround is to encode your strings of chars into strings of bytes. UTF-8 is probably the best suited encoding.