This issue will occur if the dependency services are disabled. Please make sure the following services are enabled and running.

–      DNS Client

–      Function Discovery Resource Publication

–      SSDP Discovery

–      UPnP Device Host

We can see from the security logon that successful connections are using Package Name (NTLM only):    NTLM V2

On the Server 2008 R2 box, in secpol.msc we can see LM & NTLM is refused (As it should be…)

However the client had a group policy, that had been enabled to allow a legacy application to connect to ancient Windows servers, this forced Send LM & NTLM responses

Now the bad way to fix this, is to change the server to a less secure setting (i.e. Send LM & NTLM responses)

While it is best to eliminate servers that still require LM or NTLM, and use the “refuse LM & NTLM” setting, you can compromise by changing the client policy to allow LM & NTLM, but use NLTM v2 if available, this will at least prevent you from downgrading security on your servers running more recent Windows operating systems.