Unable to browse the network

We are using NT 4.0 Server as a BDC to a Corporate Wide WAN, we have recently developed a problem browsing the network. Whenever one attempts to browse the network through “Network Neighborhood”, mapping a drive to a share, or browsing while installing a network printer, the error message, “Unable to browse the network” is returned.

Mapping to shares or printers by entering the full name of the device works just fine. No one else on the WAN reports having the same problem.