Are you running a domain or a workgroup? Workgroups require the same workgroup comm. protocol since they don't use tcp/ip for internetworking.
I am using a workgroup. I tried enabling TCP/IP and disabling NetBEUI in all the computers in the workgroup, but they refused to talk to each other.