The Exchange Mailboxes task fails with the error "Failed to open the information store." (4276287)

During a gathering the Exchange Mailboxes task fails with the following errors.

Failed to open the information store.
Time Component HResult EventID
2012-01-10T11:58:32.472Z Exchange Mailboxes 8004011D {34C7A24B-8C58-4265-80D2-6A349E874549}

Extended information was found for the last MAPI error (description: The attempt to log on to the Microsoft Exchange Server computer has failed.; component: Microsoft Exchange Server Information Store; low-level error: 0x00000000; context: 1298).
Time Component HResult EventID
2012-01-10T11:58:32.472Z Exchange Mailboxes 8004011D {305C9E0D-13E1-47BA-A550-05D292CA1345}

An error occurred while retrieving the default private information store.
Time Component HResult EventID
2012-01-10T11:58:32.472Z Exchange Mailboxes 8004011D {F6733F2B-06D0-41F2-921F-CC8E0B08A9DB}

An error occurred while performing server mailbox enumeration.
Time Component HResult EventID
2012-01-10T11:58:32.472Z Exchange Mailboxes 8004011D {C53A203C-8BAC-453d-9312-C5146EB1C5B4}