This probably has nothing to do with passwords. I would start by checking if they're being logged in with a temp profile.
Open powershell and type
$env:USERPROFILE if it has temp in the name then you'd need to fix the profile in the registry and reboot the system.
Fixing temp profiles
- Get the user's SID
- From their login type whoami /user
- Open regedit and go to HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\ProfileList
- There will likely be two SIDs for the user with one having .bak at the end
- Delete the key without the .bak on it
- Remove .bak from the other.
- Reboot and test