Windows uses several different authentication modes for Samba/SMB (ie Windows File Sharing). If the Mac is not connected to Active Directory, Apple by default only supports the oldest one, NTLMv1. That version is very unsafe because of its short keylength, so server administrators like to disable the usage of it if the network is open to non-trusted parties. The MS UAM implements NTLMv2, which has a longer keylength. Haven't used it myself in a few OS X revisions, but itt worked well back when I had reason to use it (10.2 days). Give it a try on a Mac that has problems and see if it helps.
All of this is irrelevant if the Macs are connected to an Active Directory domain. If they are, NTLM is not used at all (authentication is made using Kerberos).