You need an additional test:

if (exists $slots{$pattern[$i]}) {
  next WORDS unless $slots{$pattern[$i]} eq $letters[$i];
}
else {
  $slots{$pattern[$i]} = $letters[$i];
}
foreach $key (keys %slots)
  next if ($key eq $pattern[$i]);                #
  next WORDS if ($slots{$key} eq $letters[$i]);  # <- HERE
}                                                #
[download]

Update: fixed a code error or two...
Update2: ...or three. But it seems to work now.

buckaduck