I had created a new Exchange infrastructure for a customer:
2x Mailbox Role servers, each will have 4x 40GB databases
1x CAS and Hub role server
OK, so it sounded more impressive before I typed it out, but I digress…

I created a new database and attempted to mount it and received some cryptic MAPI error. Googled it:
http://support.microsoft.com/kb/977960

Basically AD isn’t replicating fast enough when you have multiple domains in the same forest.
Fix:
Open Exchange PowerShell
Set-ADServerSettings -PreferredServer FQDN.of.your.primary.global.catalog