We're setting up new servers and ran into the same issue. I spent half a day tracking this down, because there are many possible causes. In my case I was able to run locally without issue, and I could connect remotely using SQL Authentication, but received that error when attempting to connect via Windows Authentication. Because our SQL services run under Managed Service Accounts, we knew the problem was related to Active Directory somehow.
There were SPN-related errors in the Windows error log, and a search on the error code led me to this site which explained how to change the registered SPNs. From here we determined that the problem was that our new server had the same name as another, long-retired one, so there were duplicate SPNs in the Active Directory forest, and my new SQL instance couldn't register them for that reason.
Our fix: change the name of the new server.
But like I said, there are many possible causes. I've seen the same error message when my AD password expired.