You might want to check these out, the first fixed it for me. Ignore the Mac title, this works for anything non-windows.
Digital signing settings which assist with the addition of Apple Mac Clients to your Network
Specifically – Microsoft network server: Digitally sign communications (always)
http://support.microsoft.com/kb/555652
FYI
Everyone group does not include anonymous security identifier
(anonymous, meaning no username / password)
http://support.microsoft.com/kb/278259
