Your problem is probably the same one I described in my thread:
http://discussions.apple.com/thread.jspa?threadID=2133962&tstart=0
The problem in my case, seems to be that the SL mac is not setting itself as the master browser, so when a Windows PC is switched on, it doesn't update that computer in the finder sidebar.
You can see if this is the case, by opening terminal, and typing:
nmblookup -M -- -
If it comes back with "name_query failed to find name
_MSBROWSE_#01" then you've got the same problem as me. With Leopard, my mac would report back as the master browser.
It's got nothing to do with the firewall (I've tried turning mine off ,to no avail). Also, my workgroup is correct, and smb sharing is turned on for the user.