The method I tend to get XP networking is to run the wizard, telling the computer its part of a network with NO internet connection. (2nd page of choices) and it tends to work fine after that.

Also, try dropping the firewall (TEMPORARILY) to see if this fixes the problem.

What SP are on each machine?

Are they both in the same workgroup?

Hmm... I would ask if you access each by IP address, but the machines are not even seeing themselves.