First, i would suggest that you check to see if your licensing is setup per device or per user. you can follow this MS Knowledge base article to check that.
http://support.microsoft.com/default...97&Product=sbs
You could also try manually connecting to the domain by going onto each workstation, right click on my computer and click on the computer name tab. At the bottom you can click on the change button which will allow you to change the computer name and join it to your domain.
Also make sure that your workstations are on the same subnet as the domain. Are you using DHCP?
Windows 2000 would let you go over your licenses and allow you to add more users and devices with out blocking access. Your Event log would just get filled with license violations.