I once had similar problem in some ancient LDAP installation and it turned out that adding random 9th character was enough to pass the check while keeping the password effectively the same :)