RE: server does not exist or access denied
Your post is contradictory. You said it does not exist or access denied, but you also say it is available?
Sometimes MS updates changes the firewall settings, make sure that the SQL Server service is running on the server, then check that the protocols IP, especially is still enabled and finally make sure that the firewall is setup correctly, normally port 1433. If the service is running and protocols are still ok turn the firewall off on both machines and see if that resolves it. If so, then it is a firewall issue.