Unable to change domain credentials on Windows client PCs

Any time a user's password expires, or they want to change the password before it does, they will see the following error message:

configuration could not be read from the domain controller either because the machine is unavailable or access has been denied.

This is sometimes followed by the error:

Error code is 0xC000018B.

This is happening on Windows client OSs, 7, 8, 8.1 and Windows 10. Initially it only happened on Windows 10 PCs.

The domain functional level is Windows Server 2008 Forest functional level is Windows Server 2003.

From the domain controller (logged in via RDP, I can change my own password).

At the moment no one can change passwords using this method (from their local machine using the Windows password changer)

In the server eventlogs:

Application log - event ID 6 Automatic certificate enrollment for local system failed (0x800706ba) The RPC server is unavailable. Event 1202 occurs every so often containing the message Security policies were propagated with warning. 0x534 : No mapping between account names and security IDs was done.

In the System log, There are lots of NETLOGON source events, 2719, 5805 and 5723. For event 5723, "The session setup from computer 'COMPNAME' failed because the security database does not contain a trust account for 'COMPNAME$' referenced by the specified computer.