Remote Desktop cannot verify the identity of the remote computer

Remote Desktop login error:

Remote Desktop cannot verify the identity of the remote computer because there is a time or date difference between your computer and the remote computer. Make sure the computer's clock is set to the correct time, and then try connecting again. If the problem occurs again, contact your network administrator or the owner of the remote computer.

We have checked and the clock appears to by synced OK, but when we try ent time /set /y we get an error saying:

'The Service has not been Started' even though it is running fine???

It appears to be connected with this error:

Log Name:      System
Source:        Microsoft-Windows-Time-Service
Date:          01/07/2019 12:09:47
Event ID:      130
Task Category: None
Level:         Warning
Keywords:      
User:          LOCAL SERVICE
Computer:      PC-NAS-HP01.DOMAIN.local
Description:
NtpClient was unable to set a domain peer to use as a time source because of failure in establishing  a trust relationship between this computer and the '' domain in order to securely synchronize time. NtpClient will try again in 3473457 minutes and double the reattempt interval thereafter. The error was: The trust relationship between this workstation and the primary domain failed. (0x800706FD)
Event Xml:
<Event xmlns="http://schemas.microsoft.com/win/2004/08/events/event">
  <System>
    <Provider Name="Microsoft-Windows-Time-Service" Guid="{06EDCFEB-0FD0-4E53-ACCA-A6F8BBF81BCB}" />
    <EventID>130</EventID>
    <Version>0</Version>
    <Level>3</Level>
    <Task>0</Task>
    <Opcode>0</Opcode>
    <Keywords>0x8000000000000000</Keywords>
    <TimeCreated SystemTime="2019-07-01T11:09:47.626474300Z" />
    <EventRecordID>1457181</EventRecordID>
    <Correlation />
    <Execution ProcessID="600" ThreadID="34808" />
    <Channel>System</Channel>
    <Computer>PC-NAS-HP01.DOMAIN.local</Computer>
    <Security UserID="S-1-5-19" />
  </System>
  <EventData Name="TMP_EVENT_DOMAIN_PEER_AUTHENTICATION_ERROR">
    <Data Name="ErrorMessage">The trust relationship between this workstation and the primary domain failed. (0x800706FD)</Data>
    <Data Name="RetryMinutes">3473457</Data>
    <Data Name="DomainPeer">
    </Data>
  </EventData>
</Event>

net time /set /y
The service has not been started.

More help is available by typing NET HELPMSG 2184.