tl;dr – WTF? My FritzBox just truncated my new password because it was to long!!!1!
Holy shit! I am in the process of setting up a system wide pi-hole and my new FritzBox didn’t tell me that the new password was to long. So it just truncated it and went on with the password change. m(