There are several possible resolutions to this issue, as the error 0×80004005 simply indicates that the Exchange message store failed to start. It would help if we knew the Event ID associated with this error sequence.
Microsoft has some info here:
Per one of the moderators at MSExchange.org:
” …0×80004005 usually means there is a permissions problem. Make sure you have permission inheritance turned on from the organization level all the way down to the store. ”
There is additional information (including registry hacks) here: