I recommend putting the IP address of the Samba server in the Windows machine's hosts and lmhosts.
192.168.1.5 samba01.my.place samba01
192.168.1.5 samba01 #PRE
It wouldn't hurt, (and might actually help), if you put the windows machines' IP address in the Samba server's /etc/hosts and /etc/samba/lmhosts.
I have also found that I have to restart the Windows machines after I restart Samba.