Ok, and the DHCP service is definitely healthy?
The reason I ask is because I had a machine once that did the samed damned thing. It kept getting a 169.xxx.xxx.xxx address even though it was wired directly into a router with a functioning DHCP server.
Turned out some piece of badware was clusterboinking the DHCP service.
(Which, of course, isn't a 'router' problem as much as it was a infected OS problem)
Since it seems that fixed IPs work (pretty much except for WAN access, ) it does sound like something might be messed up there.
Have you looked at Event viewer and seen if there's any red flags?
As far as WINS goes, that's just for old Windows NT 4.0 and 98/95 compatibility, WINS isn't used for WAN access, it's mainly for LAN stuff (so you can access resources using NETBIOS names, )
You might try using a fixed IP again and set her up with OpenDNS, for now, until you can figure out what's up....