On peer to peer networks...I find it helps browsing to go into advanced TCP/IP properties, the WINS tab, and flip the radio button choice to "Enable netbios over TCP/IP".
On all computers, ensure file and print sharing is enabled in the exceptions of the firewall. If any 3rd party software firewalls....there's usually some wizard to setup local networking on the IP range behind your router.
Some computers get a screwy TCP/IP stack from years of use, occasional light malware infections...or other things that mess with the winsock. For computers that seems stubborn with this....running a TCP/Winsock repair utility can help.
http://www.snapfiles.com/reviews/WinSock_XP_Fix/winsockxpfix.html
I've found the above utility to help in some cases where 3rd party software firewalls have messed things up. Some Norton ones, and especially ZoneAlarm, are well known for messing it up.
With peer to peer networks....the computers have to communicate with each other for a period of time...and perform a "master browser election". One computer will become the master browser to the others. This is automatically done when you have a real server OS..but with desktop OS's, it can become stubborn. So when you setup a peer to peer network..sometimes it takes several hours or more of having them running...til network browsing becomes more stable. It's usually fairly quick when you setup a bunch of brand new PCs that you just took out of the box and unbuckled..but when you gather a bunch of computers that have been in use for a while, various different OSs, service pack levels, etc...this period can take longer. Sometimes going in and manually editing this IsMasterBrowser registry key is needed.
Sometimes whatever router you run can affect this as well. Some will have some impact on immediate DNS resolution. Some more biz grade routers have a feature for a local DNS table.