You might want to try to force the DNS servers by hardcoding some known working ones into the DHCP. I have had this issue a couple of times with different routers and now use Google DNS servers for my DNS. Try hardcoding the DNS in one of the machines that is failing and see how it works. If it solves the problem then set the same DNS in the router DHCP page.