I would not recommend using NetBEUI. You will significantly increase your network traffic. TCP/IP with a WINs server is more efficient.
Check the following on your clients:
1. Make sure that the Workgroup name = Domain on your clients.
2. If your clients are getting the WINs server address via DHCP, try manually adding the WINs server IP addresses on the clients.
3. On all of your Windows 9x machines that have File and Print Sharing installed, set the Browse Master to DISABLED. You will find this under Network Neighborhood -> Properties -> File and Print Sharing -> Properties. This will prevent your clients from getting incomplete Browser information from a 9x machine, and will force them to look to your NT servers instead.