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();

Run fixmapi.exe under the Windows\System32 directory with Outlook open and then reboot the system for setting to take affect (when run, it looks like nothing is happening but it is so check task manager to confirm it has finished).