The OSX firewall needs to allow the broadcasts from the Windows network for your Mac to be able to "see" which systems are available.
Lion is more strict in its default firewall rules as the previous versions and it won't do this "out of the box".
If you tell the Mac to allow Sharing files/printers it will open the firewall for this. Even if you are not really sharing anything from the Mac, but just using the Mac as a client for other shares.
I can't recall the exact steps from the top of my head. I'm in the office now which is Windows only. But I've got 2 Lion Mac's at home that have no issue accessing Windows shares/printers.
P.S: If you have consistent issues with establishing connections with a specific Windows box you can install the "Bonjour printer services for Windows" (free download from Apple) on the Windows machine. This makes the Windows PC advertize itself to any Mac on the network using the native Apple protocol, which is quicker and more reliable than the normal Windows broadcast mechanism.