If your keysvalues look duplicate, most likely, there are things you don't see. Most likely it's whitespace at the end of one keyvalue. Inspect your hash through Data::Dumper, and best concentrate on keysvalue that should be equal but aren't:

use strict;
use Data::Dumper;

my %hash = (
  'Hello ' => 'world',
  'The'  => 'world ',
);

print Dumper \%hash;
[download]

If your hash is too large to conveniently dump, you can find out one of the values that are duplicate and create a copy of the hash:

for (keys %bad_hash) {
    if ($bad_hash{$_} =~ /orl/) { # because we're looking for "hello"
        $hash{ $_ } = $bad_hash{ $_ }
    }
}

print Dumper \%bad_hash;
[download]

You also might run into encoding issues where two different octet sequences (that actually compare as unequal) encode to the same glyph sequence. But as Perl 5.8 internally uses UTF-8, that shouldn't be a problem. In any case, it would help to see some more yet still small code and some really small dataset (2 lines) that reproduces the problem.

Update: Realized this is about values, not keys.