Para mim, consegui evitar essa mensagem:
Bad: new password is just a wrapped version of the old one
executando $sudo passwd <my_username>
em vez de apenas $ passwd
É óbvio que esteja ciente das implicações de segurança, mas pelo menos permite isso agora.