I was just thinking - we had a computer at work that couldn't communicate across the network, and it was eventually traced down to Norton Internet Security's firewall blocking ICMP and NetBIOS protocols - does the PC trying to connect to the router have any software firewalls active? It could be blocking access to the router you see. NetBIOS needs to be allowed so that the router can assign the PC a network address, and ICMP is needed for communication between a host (PC) and an Internet gateway (router).
Will try and help out a bit more tomorrow...
Nite