I am also getting errors on trying to open the information store on new mail boxes. Existing boxes work fine, but, if I create a new mailbox and try to access it in outlook I get the message - "The information store can not be opened".
Have you rcvd any responses to your post?