If you cannot map a drive to the Alfresco CIFS server then it's likely a name lookup problem. Check whether you are using WINS or broadcast lookups on your LAN. If you're using broadcasts, is your network split into more than one subnet? Did you change the broadcast mask setting in the file-servers.xml configuration file? Do you use NetBIOS name scopes on your LAN? (nbtstat -n should show if a scope id is set).
If a PC cannot access the Alfresco CIFS server you could try adding an entry to the lmhosts file (in windows\system32\drivers\etc), there's usually a sample file in that folder, you may need to create the file. Then try and access the CIFS server using Start->Run and enter \\<Alfresco servername>.
You could also try doing some name lookups using nbtstat, again from any of the PCs that are having trouble accessing the server. If you try the following commands to see which are successful :-
nbtstat -a <Alfresco server name>
nbtstat -A <server ip address>
nbtstat -a <Windows server name>
