SQL: A network-related or instance-specific error.

I was getting this kind of error:
"SQL State: 08001, SQL Error Code: 0
A network-related or instance-specific error has occurred while establishing a connection to SQL Server. Server is not found or not accessible. Check if instance name is correct and if SQL Server is configured to allow r." (yes, it was strangely truncated).

In addition to this article about Resolving “A network-related or instance-specific error occurred while establishing a connection to SQL Server…”, which has excellent 7 steps to follow, I have discovered another issue.

If you still cannot connect to your SQL Server from you local machine and have confirmed that the server is accessible from another computer, you have to check if you have only one SQL Native Client installed. I my case there were two of them and obviously the DLL files got messed up. Just uninstall all SQL Native Clients, remove both sqlncli10.dll and dbxmss.dll from /system32 (if any is present after the uninstall) and reinstall the latest SQL Native Client.
That solved my problem.