From your description the problem might be the GC services registration in DNS.
Exchange server needs correct Global Catalogs pointers to be able to search/authenticate users.
So, you might want to start trying this:
Stop all Exchange Services
On each DC (GC) run: IPCONFIG /flushdns && IPCONFIG /registerdns
Next, on the Exchange Server run: IPCONFIG /flushdns && I*CONFIG /registerdns
Still on Exchange Server, run NBTSTAT -R (captial R)
Next Step is to force a Directory Replication
Try and start the Exchange Services
Let us know how it went.