I purchased a new modem/router today, and while all seems to be mostly working as expected, I can no longer resolve machine names to their IP addresses. I have an iMac and a Macbook Pro, both running Snow Leopard (fully patched). I also have a Windows 7 laptop, but that can resolve the IP addresses successfully, which leads me to believe it may be an OSX config issue. The IP addresses are assigned using the routers DHCP server, and the router can successfully display the machine name.
The new router is a Belkin Share, and it is replacing a D-LINK DSL-G604T. When using the latter router, I had no difficulties resolving IP addresses from machine names. I spent 1/2 an hour on the phone to Belkin support, and they also thought it sounded like an OSX config issue, but were not knowledgable enough with OSX to be able to assist me.