This error also happens when the user is spelled wrong or the password is incorrect. Microsoft does provide us with an confusing errormessage which does not always describe the actual problem
I just spend half an hour being able to create a database connection without any problem using a full access account but having the 'incorrect sql native client' when using a read-only account (which turned out to be incorrectly spelled).
I had run into the same issue and that error message led me the think I was having an issue with the native client. But I had another geodatabase that was working fine so it had to be something else. Went back to read through some documentation and I realized that it was actually a permission problem.
"Registering your data does not grant the ArcGIS Server account permissions to access your data. Before registering your data, you'll need to ensure that the ArcGIS Server account has at least read permissions to the data stored in folders, in databases, or in enterprise or workgroup geodatabases that are accessed using operating system authentication. To learn more about this process, see Make your data accessible to ArcGIS Server."
About registering your data with ArcGIS Server—Documentation | ArcGIS for Server
To correct this issue, I simply had to install the Microsoft ODBC Driver 11 for SQL Server.
Check out this link: