"Just not starting services" could be absolutely anything though.
Are there any other Exchange related eventlog entries?
Have you checked your DNS, name resolution is one thing, its not it all however.
Can you resolve the FQDN?
Can you browse from the Exchange server to the DCs NETLOGON share? Via UNC? Via IP?
Checked the Exchange computer account in AD?
Is this an existing environment, a change in an existing one, a new one?