I faced the same problem and the solution is to add the user that starts the ArcGIS Server service to the SQL Database. Say that .\arcgis is the ArcGIS Service user that is shown in the services window (services.msc command). You have to add this same user to the SQLGeodatabase.
To do this you only need to execute the "Add User" tool. This tool either in the toolbox, or right click in the geodatabase\Administration\Add user. There you have to put NameOfYourServer\arcgis as the user to create. In my case was like this:
One other thing to take into account, if you are running a multi-machine site make sure that the SQL Native Client is installed on both machines. If you do it on one but not the other, it will error out with this message.
I'm running into this same error message, and I'm sure it's just user error on my part. We have 10.5 desktop on our local machine, arcgis server (enterprise) basic on a 2016 server, and our sde database is sitting on another server(2008). I have 2012 Server Client installed on my computer. Where am I going wrong...btw I am no DBA...just fumbling through it.
I had exactly the same problem, despite the arcgis account already been a database user.
I solved this issue by installing the Microsoft® ODBC Driver 11 for SQL Server, avaible in http://www.microsoft.com/en-us/download/details.aspx?id=36434.
I found this tip at Unable to register gdb with the server due to sql server client incompatibility - Geographic Informa...
I recently had a similar issue and got here through googling. Our IT needed to change the architecture of our DBs and this resulted in a change the SDE DB Server host name (not the DB name). I was able to get my regular SDE connections in Pro and other maps working fine with a quick host change, but I couldn't get the Data Store to update on my Portal site. I created a new SDE connection file with the new host and every time I imported I got a error like this. The SQL DB had my the correct Server Service AGS user, but it turned out the new DB Server did not have that user. Adding that user to the DB server (along with the DB) solved the problem for me. Just wanted to drop this in here for anyone else that might get here with a related problem. xkcd: Wisdom of the Ancients