Warning 2601, errors 2604 and 2501 -- In the event viewer.
A series of things can fix this issue.
1. Verify the Exchange server(s) is a member of the "Exchange Servers" and "Exchange Install Servers" groups. Verify that these groups are under the manage/audit rights for the default domain policy (Under local policies -> user rights assignments).
2. It could be related to the order Exchange services start up. I think this was the right order:
"Microsoft Exchange Active Directory Topology Service"
"Microsoft Exchange Anti-spam Update"
"Microsoft Exchange EdgeSync"
"Microsoft Exchange File Distribution"
"Microsoft Exchange IMAP4"
"Microsoft Exchange Information Store"
"Microsoft Exchange Mail Submission"
"Microsoft Exchange Mailbox Assistants"
"Microsoft Exchange POP3"
"Microsoft Exchange Replication Service"
"Microsoft Exchange Search Indexer"
"Microsoft Exchange Service Host"
"Microsoft Exchange System Attendant"
"Microsoft Exchange Transport"
"Microsoft Exchange Transport Log Search"
"Microsoft Search (Exchange)"
3. The one that actually fixed the issue for me was to simply restart the Net Logon service and the "Microsoft Exchange Active Directory Topology Service."