All the stuff goes through the motions, 0 Errors, the Exchange tabs appear in the AD user properties, but no mailboxes are created.

I told the client we may have to uninstall and reinstall Exchange (always a fun thing to do).