I had this problem with fresh new Windows 7 PC.
XP machine had media server running and that worked. From Windows & machine I could browse all the media on the XP box no problem.
Despite having same username/password on each PC and same workgroup neither PC could see the other on the network.
Pings worked using IP addresses e.g.
Ping 10.0.0.9 worked from Windows 7 (to XP)
and
PING 10.0.0.14 worked from Windows XP (to Windows 7)
but
Ping XPBOX failed
My solution (as not running DNS on the network) was to edit the hosts file on the Windows 7 machine to add an entry like
10.0.0.16 W7BOX
The problem here is saving the changes.
You need to right click and select 'Run as Administrator' for notepad.exe even if you are an administrator!
This fixed the problem for me.
PS
hosts file in located in
c:\windows\system32\
drivers\etc
and must not have any kind of extension (i.e it is 'hosts' not 'hosts.txt' etc)