My current client is setting up an entirely new set of machines for their project running Windows Server 2008, and this includes a new Domain Controller and so we just went through the adventure of figuring out how to have a Windows Server 2008 box join a domain. If you're having issues with this, the trick is two things:
- Change your network properties to be a Private network instead of a Public network.
- Go to Windows Firewall and turn it off.
Don't worry, once you're on the domain it will by policy re-enable the Firewall, so this is just a temporary change.