My first inclination is to use arrays, as Zaxo did above. But I think maybe hashes would be easier:

my %ih;

$ih{$hash{$_}}{$_}++ for keys %hash;

print 
  for grep { keys %{$ih{$_}} > 1 } keys %ih;
[download]

I also think a while/each might be nice here, as it makes the inversion of the hash a bit clearer:

while ( my($key,$val) = each %hash ) {
  $ih{$val}{$key}++;
}
[download]