Most probably a false positive due to a hash collision. The hash function is probably telling your program that the string only has a single character changed, but multiple characters may have changed and the same hash value has been computed.

To avoid this, maintain a Map<Long, String> for each hash value -> string, then when you think you found a solution, double check that the difference is indeed one letter. See my submission for an example.