Thanks for the tip - problem solved! My router is indeed a belkin router (the standard 4 port model) and when I stuck a different router in between, knoppix was able to complete DHCP setup on all computers. Since the actual physical network card worked in a different computer, I can't imagine how the computer itself would impact DHCP negotiation, but such is the case.

Belkin router owners BEWARE!

I find it disturbing that a windows security update can also break linux networking, as you discovered. I didn't notice a solution from scanning the many posts from that thread, so what is the solution, is it to reset the NIC EEPROM to factory settings? Also I'm very curious why M$ found it necessary to step beyond the OS and change settings in the NIC. I gather that prevents a hacker from spoofing a certificate? I wonder what the technical details (what kind of hacking technique) are of how that is necessary to maximize security in windows XP, and is that something that needs to be addressed to maximize security in Linux also?