Deleting the user and creating it again with the same password worked fine, so it seems the "Change password" function is just broken in this DNN version.

So, any updates on this? Not being able to change the passwords for users in DNN is a real problem as deleting them and then recreate them is not a good solution at all.

It seems like we were able to find the source of this. Turns out that unless you have Password Reset enabled, it won't work to change the password password even logged in as Host. This I would consider to be a bug since the Password Reset in my opinion is not the same thing as changing password as super admin. So to change password, you need to reenable Password reset, change the password, and the disable Reset password again (if you want to make sure users can't change passwords themselves).