I just upgraded to ArcGIS Desktop 10.4.1 on my ArcGIS Server machine. I could not connect via an SDE connection at first but I uninstalled the 2008 SQL Native Client and installed Microsoft® ODBC Driver 13 for SQL Server (we also just upgraded to SQL Server 2014 a few weeks ago) on our ArcGIS Server machine and the SDE connection worked fine after that.
However, I tried a query on our map services and get the error regarding the old client (see screenshot). I did the same thing on the web server machine (uninstalled 2008 and installed ODBC Driver 13), but it's still not working. Do you think I should just uninstall all references to 2008? I'm not sure why all those SQL Server 2008 program files are installed on our web server since we have a separate machine for SQL Server as well.