XADM/Exch2010/ Exchange EMC cannot access the AD configuration data

In an Exchange 2007 Environment the Exchange Management Console may try to connect to a non-existing DC/GC, i.e. a DC/GC, which was earlier in the environment, but was later demoted and removed from the environment. An automatic failover to an existing DC/GC in the environment does not take place and the Exchange Management Console may close, showing an error message You will notice this Error in application Log:

Log Name:    Application
Source:        MSExchange Configuration Cmdlet - Remote Management
Date:           12/9/2009 9:24:31 AM
Event ID:      4
Task Category: General
Level:           Error
Keywords:     Classic
User:            N/A
Computer:     MAIL01.FQDN.COM

Description: (PID 5984, Thread 10) Task Get-ExchangeServer writing error when processing record of index 0. Error: Microsoft.Exchange.Data.Directory.SuitabilityDirectoryException: An Active Directory error 0x51 occurred when trying to check the suitability of server 'OLDDC.FQDN.COM'. Error: 'Active directory response: The LDAP server is unavailable.' ---> System.DirectoryServices.Protocols.LdapException: The LDAP server is unavailable.

(PID 11100, Thread 24) Task Get-MailboxDatabase writing error when processing record of index 0. Error: Microsoft.Exchange.Data.Directory.SuitabilityDirectoryException: An Active Directory error 0x51 occurred when trying to check the suitability of server '<FQDN of Your Server>'. Error: 'Active directory response: The LDAP server is unavailable.' ---> System.DirectoryServices.Protocols.LdapException: The LDAP server is unavailable.
   at System.DirectoryServices.Protocols.LdapConnection.Connect()
   at System.DirectoryServices.Protocols.LdapConnection.BindHelper(NetworkCredential newCredential, Boolean needSetCredential)
   at Microsoft.Exchange.Data.Directory.SuitabilityVerifier.CreateConnectionAndBind(String fqdn, Int32 portNumber, NetworkCredential credential)
   --- End of inner exception stack trace ---
   at Microsoft.Exchange.Data.Directory.SuitabilityVerifier.CreateConnectionAndBind(String fqdn, Int32 portNumber, NetworkCredential credential)
   at Microsoft.Exchange.Data.Directory.SuitabilityVerifier.IsServerSuitable(String fqdn, Boolean isGlobalCatalog, NetworkCredential credential, String& writableNC, LocalizedString& errorMessage)
   at Microsoft.Exchange.Data.Directory.ConnectionPoolManager.GetConnection(ConnectionType connectionType, ADObjectId domain, String serverName, Int32 port, NetworkCredential credential)
   at Microsoft.Exchange.Data.Directory.ConnectionPoolManager.GetConnection(ConnectionType connectionType, NetworkCredential networkCredential, String serverName, Int32 port)
   at Microsoft.Exchange.Data.Directory.ADSession.GetConnection(String preferredServer, Boolean isWriteOperation, Boolean isNotifyOperation, String optionalBaseDN, ADObjectId& rootId, ADScope scope)
   at Microsoft.Exchange.Data.Directory.ADSession.GetReadConnection(String preferredServer, ADObjectId& rootId, ADRawEntry scopeDeteriminingObject)
   at Microsoft.Exchange.Data.Directory.ADGenericReader.GetNextResultCollection(Type controlType, DirectoryControl& responseControl)
   at Microsoft.Exchange.Data.Directory.ADPagedReader`1.GetNextResultCollection()
   at Microsoft.Exchange.Data.Directory.ADGenericPagedReader`1.GetNextPage()
   at Microsoft.Exchange.Data.Directory.ADGenericPagedReader`1.<GetEnumerator>d__4.MoveNext()
   at Microsoft.Exchange.Management.SystemConfigurationTasks.GetDatabaseTask`1.WriteResult[T](IEnumerable`1 dataObjects)
   at Microsoft.Exchange.Configuration.Tasks.GetTaskBase`1.InternalProcessRecord()

The issue even does not go away even if you go into the Exchange Management Console and change the Configuration Domain Controller according to http://technet.microsoft.com/en-us/library/aa998227.aspx