I was facing this on a VM setup, where the service account of my SQL Server service is a domain account. The DC is also a VM. Here were the symptoms:

While backing up the database to the UNC share, I was getting an error:

"Operating system error 1398" (There is a time and/or date difference between the client and server)

First things first, I did not have any timesync issue. That would have affected Kerberos and everything else around it.

Secondly, doing a xp_cmdshell ‘dir \uncserverpath’ would result in the same error, so this was not unique to the backup code (obvious, but better to check.)

Interestingly, if I opened up a new CMD prompt ‘running as’ the SQL Service account, and execute the ‘dir’ command, then the network share contents were listed (i.e. no error message.)

So then it dawned to me that at the time the SQL Service was starting up, there was a race condition wherein the DC was not yet ‘fully’ started. This caused the usage of stale Kerberos tickets and in turn caused the above error.

Only way to fix this was to restart my SQL instance, because then the expired Kerberos ticket would be replaced with a freshly authenticated and timestamped one. Sad, but true.

Hope this helps someone out there!