Hmmm, you rebooted all the machines?
Well, you can force it, but you have to do so in each Windows machine. If you're running Linux, you'll do something similar in samba.conf.
1. In the Registry (start, run, regedit.exe), navigate to HKEY_LOCAL_MACHINE\System\CurrentControlSet\Services\Netbt\Parameters
2. Look for the key NodeType (not DhcpNodeType). If it already exists (it probably does not), then go to step 4
3. Right click on the Parameters key, create Key, Dword, called "NodeType"
4. Right click on the NodeType key, modify its value from it's current value to 1 (hex value is 0x1, decimal value is just 1).
5. Exit from RegEdit and restart that machine.
After making this change, the IPCONFIG /ALL configuration should have changed, reflecting the node type as Broadcast. Doing this on each machine affected should help them find one another.
To reverse this change, repeat the above steps but delete the NodeType key. This will return the default behavior appropriate for your Windows version and DHCP parameters.