Exchange 2010 Services not starting after replacing/upgrading Domain Controllers

After upgrading our domain controllers to Windows Server 2012 our Exchange 2010 server was not allowing connections.  After a reboot it would not allow services to start and would not login completely, it would hang during login process.  After investigation we found Exchnage services trying were start and stopping.  Below are the erros and I'll post what we did to fix in an answer after this post.

Log Name:      Application
Source:        MSExchange ADAccess
Date:          2/5/2013 10:35:41 PM
Event ID:      2114
Task Category: Topology
Level:         Error
Keywords:      Classic
User:          N/A
Computer:      EXCHANGE2010.domain.com
Description:
Process MSEXCHANGEADTOPOLOGYSERVICE.EXE (PID=3164). Topology discovery failed, error 0x80040a02 (DSC_E_NO_SUITABLE_CDC). Look up the Lightweight Directory Access Protocol (LDAP) error code specified in the event description. To do this, use Microsoft Knowledge Base article 218185, "Microsoft LDAP Error Codes." Use the information in that article to learn more about the cause and resolution to this error. Use the Ping or PathPing command-line tools to test network connectivity to local domain controllers.

Log Name:      Application
Source:        MSExchange ADAccess
Date:          2/5/2013 10:35:41 PM
Event ID:      2080
Task Category: Topology
Level:         Information
Keywords:      Classic
User:          N/A
Computer:      EXCHANGE2010.domain.com
Description:
Process MSEXCHANGEADTOPOLOGYSERVICE.EXE (PID=3164). Exchange Active Directory Provider has discovered the following servers with the following characteristics:
 (Server name | Roles | Enabled | Reachability | Synchronized | GC capable | PDC | SACL right | Critical Data | Netlogon | OS Version)
In-site:
old-dc1.domain.com      CDG 1 0 0 1 0 0 0 0 0
old-dc2.domain.com      CDG 1 0 0 1 0 0 0 0 0
 Out-of-site:


Log Name:      Application
Source:        MSExchange ADAccess
Date:          2/5/2013 10:35:41 PM
Event ID:      2102
Task Category: Topology
Level:         Error
Keywords:      Classic
User:          N/A
Computer:      EXCHANGE2010.domain.com
Description:
Process MSEXCHANGEADTOPOLOGYSERVICE.EXE (PID=3164). All Domain Controller Servers in use are not responding:
old-dc1.domain.com
old-dc2.domain.com