That was a lot of information
My blind guesses, issues with the previously setup networked drives? Re-authenticating with the new systems? Both of these might have to do with windows caching some of the data, possibly a simple restart of the workstations might take care of it?
There should be *something* in the logs when these access attempts are made, that might be helpful in diagnosing this problem.
Also, check the /etc/hosts and /etc/hosts.deny /etc/hosts.allow files (if they exist) to make sure nothing hard coded in there is affecting these updates.