Surely a common router/firmware incompatibility?
The Windows clients are not working with their local DHCP provider, which is on the LAN interface(s) of their domestic router.
DHCP isn't hard, but there is quite a bit that can be set there that usually isn't.
Are these routers putting out a field:value that something in the Windows patch is choking on? It wouldn't be the first time that Microsoft have tried to rewrite the rules of basic networking or web protocols to suit their own means, is it?