Are both machine members of the same workgroup or domain?
Are both machines in the same subnet? Browsing between subnets only works if you have a WINS server where machines on both sides of the router register their addresses.
Is the Computer Browser service running? Launch the Services.msc console and check the service list.
Have you turned off NetBIOS-over-TCP/IP on one or both of the machines? This is done via Networking and Dial-up Connections | Local Connection Properties | Advanced | WINS. NBT must be enabled for browsing to work.
Have you configured the interfaces to use a WINS server? If so, is the WINS server running and are the correct addresses registered? Does the Master Browser appear in the service list?
Do you have any other servers in the lab that might be taking over as Browse Master but not communicating correctly with the two test machines? (This is a long shot, but worth a check.) Get a copy of the Windows 2000 Resource Kit and use the Browser Monitor (Browmon) to identify the Browse Master. If Browmon can't find any Browse Master for your workgroup/domain, or if the Browse Master it finds isn't the test server, then rework your lab infrastructure.
This was first published in March 2001