I investigated the issue, firstly checking the event logs on each Domain Controller and also the server which held the roaming profiles.
On one DC, I found event 2103 in the Directory Services log.
‘Active Directory Domain Services database has been restored using an unsupported restoration procedure’.
As a result, Windows had paused the Net Logon service, therefore this domain controller would no longer be able to provide authentication or register DNS records. (Those users experiencing issues were trying to autheticate to this domain controller).
The Net logon service "Maintains a secure channel between this computer and the domain controller for authenticating users and services. If this service is s topped, the computer may not authenticate users and services, and the domain controller cannot register DNS records."
To fix this issue. on the domain controller experiencing the issue,
1) Check the Registry value "HKLM\System\CurrentControlSet\Services\NTDS\Parameters, for "DSA Not Writable" (REG_DWORD) with a value of 0x4.
2) Delete "DSA Not Writable" (REG_DWORD) from registry and reboot the server.
3) Check the Net Logon service is started and the Direcory Services event log is clean of new errors or warnings.