You should have already done this but you didn't mention it in your post. Try to find the sequence of events that is being taken by the computers involved in the network connections. Look at the log files on the Linux server. Look at the log files on the clients. I have found that network connectivity problems are often related to security.
If you find that the problem is, in fact, coming from the Microsoft Services for Unix software then consider the alternative. Put Samba on the Linux server and make it a part of the M$ network. That will remove a network protocol from the client once M$ 4 Unix is removed and you will enjoy the convenience of having one security model for network access. This will simplify your life and reduce the possibilities of creating security weaknesses.
I have expressed in other discussions that I am NOT a fan of NFS. I love Linux. I hate NFS. I believe that the SMB network protocol is technically better than NFS. And, just in case you're wondering, SMB was created by IBM, not M$. That's probably why M$ hasn't stopped the Samba software project, but let me stress PROBABLY. I really don't know for sure.