Connecting to your Exchange 2010 Organization fails with the error: "MAPI was unable to open the (4268014)

Full Text of Error:

MAPI was unable to open the message store for the mailbox 'ServiceAccount'. Please ensure that the gathering account has Full Access permissions to the mailbox and that the mailbox server is operational.
Time Component HResult EventID
2012-08-27T11:47:05.300Z Exchange Server Validation 8004011D {CE74471D-4BA1-40cd-842C-EC13A3A14A78}

The following error occurred during the processing of a given gathering: MAPI_E_FAILONEPROVIDER.
Time Component HResult EventID
2012-08-27T11:47:05.316Z Internal Processing 8004011D {E4AE5340-3285-4BCC-881A-E667070E4773}