MAPI_E_FAILONEPROVIDER Unable to log into the message store on the server (4301868)

While trying to connect to a Windows NT4 Exchange 5.5 Organization the error is,

Unable to log into the message store on the server. The account does not have sufficient Exchange rights to access the message store.

Details:
MAPI_E_FAILONEPROVIDER

Probable Cause: You do not have administrative access to the server, or the MAPI subsystem has been broken by another application.

Object: /o=XYZ/ou=HQXY/cn=Configuration/cn=Servers/cn=Exw01/cn=Microsoft System Attendant; Context: Opening the default private information store.;
Server:/o=XYZ/ou=HQXY/cn=Configuration/cn=Servers/cn=EXW01; DC:ABC; Method: QExchangeWidget::GetDefaultMessageStore; Calling OpenMsgStore();