Hmm... Check the non-working machine and see if it's using Client for Microsoft Networking in network properties. Perhaps that's the difference.
Oh, BTW, you can install NETBEUI on XP if you have a mind to, it's in the VALUEADD directory on the CD. Also, here's a direct download of the XP NETBEUI files:
http://www.onecomputerguy.com/software/xp_netbeui.zip
When you click on that link, it should download the file on the spot, it contains a batch file to move the two files to the correct directories, then you install NETBEUI just like any other protocol.