And one more thing: is ICS (Internet Connection Sharing) enabled on these machines? Also, if you open TCP/IP protocol properties, click Advanced and then click the DNS tab - what does the “DNS suffix for this connection” box show?
Thanks