Kenneth Fisher notes a behavior change for SQLCMD with SQL Server 2014 and later:
This error is seen when using a Windows Authenticated id and NTLM or an untrusted Kerberos connection. From what I understand, with Kerberos the client (SQL in this case) gets a ticket containing your credentials, it can then pass this ticket on to other servers that trust it to have authenticated you to be sure you are who you say you are. Note the mention of trust. This means that even if you are using Kerberos if the two servers aren’t in a trusted relationship then you will still see the error. And NTLM doesn’t have the option to do this at all (again, not sure why).
At this point it’s important to note that this is not a SQL Server error. You will see this error in other places where you bounce across multiple machines and aren’t using Kerberos with a trusted relationship. I’ve seen it when trying to access files before (it was a weird situation admittedly).
Read on to learn about the ramifications of this behavioral change and how you can prevent double-hop problems when running newer versions of SQLCMD.