For the sake of others easily finding this magical solution, can you maybe post the error messages for all the services that fail, so that other suckers like me can find it in less then 1 day, as this is not only a pain to implement but also a pain to find...
i.e.
----------------------------------------------------------------
Event Type: Error
Event Source: Service Control Manager
Event Category: None
Event ID: 7009
Date: 8/6/2008
Time: 2:42:20 PM
User: N/A
Computer: EX1
Description:
Timeout (30000 milliseconds) waiting for the Microsoft Exchange Mailbox Assistants service to connect.
For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.
------------------------------------------------------------------
Event Type: Error
Event Source: Service Control Manager
Event Category: None
Event ID: 7000
Date: 8/6/2008
Time: 2:42:20 PM
User: N/A
Computer: EX1
Description:
The Microsoft Exchange Mailbox Assistants service failed to start due to the following error:
The service did not respond to the start or control request in a timely fashion.
For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.