Using a similarity score like Levenshtein distance, fail if levenshtein(username, password) < 6 ? Or even something to catch permutations too, like this:
levenshtein(sort_by_chars(username), sort_by_chars(password)) < 6
That seems like it would cover the worst abuses, without prohibiting “Ed” from signing up with a nice long password, and it’s easy to explain accurately: “your username and password are too similar”. I haven’t looked for undesirable edge cases but I can’t think of any at the moment.