I had this problem once. I had to enable the Guest user account on each PC that was sharing resources (files and/or printers) to eliminate the problem.
Several of you seem to have abandoned your firewall software. It seems that you were daunted by network problems, and figured that firewalls just aren't worth the hassle. They are. Let me give you a little guidance:
1) Set up your network first, and prove to yourself that it's fully functional. If any of your PCs have firewall software already, disable that software until full network functionality is proven.
2) Deploy your firewall software on one PC at a time, and ensure that it is properly configured on that PC before deploying on the next one. If any of your PCs had firewall software before you got to this step, enable that software on one PC at a time, ensuring that each PC's firewall is properly configured before moving on to the next one. It's very difficult to troubleshoot network problems when one has two or more PCs with improperly configured firewalls (and this is exactly what some of you encountered).
Personally, I don't like the Internet Connection Firewall built into Windows XP. It can't be configured to suit one's needs or wants. Because it doesn't generate any reports, its effectiveness can't thoroughly be known. I use and recommand the ZoneAlarm family from Zone Labs:
A) It has an intuitive and uncluttered interface.

http://images.thetechguide.com/forum/public/style_emoticons/<#EMO_DIR#>/cool.gif\' class=\'bbc_emoticon\' alt=\'B)\' /> It can be installed and configured relatively quickly.
C) It generates an activity report so that one can see what is blocked and what is allowed.
D) It monitors outbound traffic (which can be generated by viruses and spyware) as well as inbound traffic -- the mark of a good firewall.
E) It can be configured to automatically check for updates, upon which it notifies the user.
F) It is rated the best family of personal firewalls by more IT reviewers and pundits than any other family of personal firewalls.
G) There is a free edition for personal use.
That's my two cents' worth.
jarigali at bigfoot.com