On some recent Exchange 2010 builds I noticed that sometimes the Exchange services would fail due to a lack of connectivity with Active Directory. I noticed that the network location had changed from Domain and was listed as Public even though the server had a single connection which was on the internal corporate network.
A fix was released on this issue and can be downloaded from Microsoft.
The network location profile changes from "Domain" to "Public" in Windows 7 or in Windows Server 2008 R2
Update: 19-9-2012: One thing I have noticed is that restarting the "Network Location Awareness" service will cause Windows to re-evaluate the firewall policy to apply which is great to avoid a restart. However sometimes I could not restart the service and I would get a message saying that "Error 1051 A stop control has been sent to a service that other running services are dependent on". Stopping the one dependent service "Network List Service" did not change the behaviour. To correct this, make sure that the Network and Sharing Center window is closed. If that window is open to view the active networks, then that stops the services restarting.
Update 21-6-2014: On a recent customer engagement I saw this issue again. In that situation it was interesting that the network location was changing after the server had been running for a while. The network in question was experiencing other issues that seemed to exacerbate this issue. As a best practice please read the Exchange 2010 tweaks post and ensure that all the recommended cluster hot fixes have been installed.