You might be interested in the Text::Levenshtein modules which supply an algorithm for measuring the similarity between two words. From the Pod:

use Text::Levenshtein qw(distance);

print distance("foo","four");
# prints "2"
[download]

It prints "2" because it takes 1 change ('o' -> 'u') and 1 addition ('r') to change 'foo' into 'four'. This would help you catch people trying to change their passwords just by adding an extra character on the end, like 'password' -> 'passwordX'.

HTH
ViceRaid

(Though I like Abigail's suggestion above a great deal, and had never realised you could do that. Thanks.)