It seems to be related to the hash table, yet you don't show us the table.

Anyway, one problem with your code is that you iterate over a hash, abort in the middle and don't reset the iterator.

Iterating over a hash is a bad idea anyway - just store it the other way round (ie turn the values into keys and the other way round), and do a lookup:

# assuming you have no duplicate values:
my %mapkey = reverse %keymap;

sub findCharacterAsKey {
    my $loebnerLetter = shift;
    if (exists $mapkey{$lobnerLetter}) {
        return $mapkey{$lobnerLetter};
    } else {
        warn "Could not resolve '$loebnerLetter'";
    }
}
[download]

Since you have to do the inversion of the hash only once, it'll be much faster and correct this way.