Connecting Time Machine to a server: "Your password on the server X needs to be changed."

I am trying to reconnect Time Machine to a backup server. It was used for Time Machine in the past.

After entering my credentials, I get the following error:

Your password on the server “server” needs to be changed.

You must change your password in order to access the server.

I am not sure what to make of it. I have reset the user password several times, tried shorter passwords, fewer special characters, etc. I keep getting this error.

I get the same error when trying to connect to the server from Finder. Some questions suggest the error might be permission-related, but this user has read-write access and I have not changed its permissions.

I looked at similar questions (about "MacOS Server") and I have deleted all Time Machine entries from Keychain already.

When I enter invalid credentials, the login dialog shakes, so I know the credentials are valid.

Solution 1:

Even though the credentials were valid, I had configured my server to force all users to reset their passwords after logging in for the first time.

So the error message really means: please login to the server interface with your credentials, change your password then come back to Time Machine.