"Could not decrypt key" upon login

So, it appears that I can create new users who can log in successfully but I cannot reset the password of existing users because I get the same “Could not decrypt key” message as a result of occ user:resetpassword.
Does anybody have an idea how to remedy this situation? I badly need to get all my existing users back to a working state.