What does this command do: sudo dscl . passwd /Users/administrator thePassword
Ah, it turns out that that is the correct way to change a user's password when using sudo. If you don't use sudo, only then do you need to provide the user's old password.

My problem was that there was a '$' character in the password, which I didn't escape. Consequently, the passwords were cut off to before the $ character.