I solved a very similar problem on my network last night:
Linksys WRT54G Router V1.0
3 XP Pro Machines
1 Win 7 machine
All were working, pinging and sharing fine until I replaced the router with a WRT54G V8.0. After that, I could only ping some machines from some others, and could not share any drives or printers.
I was positive this had to be a router problem, but it turns out it was a weird McAfee firewall issue (probably something to do with how McAfee relates to the routers MAC address).
The solution that worked for me was as follows:
The range of trusted networks in the McAfee Firewall settings was correct (192.168.1.1 -> 192.168.1.255). However, after trying everything else I could think of, I deleted the rule that allowed this trusted range within the McAfee Firewall settings. I then recreated it exactly as it was, and Voila! I could now ping that computer from every other computer. I did the same on all machines and the problem was solved.
I hope this helps someone.