MAPI Error/Public folder permission issue - Exchange 2003

Hi,

I recently undertook the task of rebuilding an exchange server after the previous one went belly up.

I now have email, both externally and internally, working. The only issue that remains is accessing the newly created public folders. I can create a folder in EM but when I attempt to access the permissions I receive an error relating to a MAPI issue:

'The MAPI call 'OpenMsgStore' failed with the following error:
The attempt to log on to the Microsoft Exchange Server computer has failed.
The MAPI provider failed.
Microsoft Exchange Server Information Store
ID no: 8004011d-0512-00000000'

The store is mounted. I presumed this was a permission issue, but after giving everyone full access (to test) to the top level all the way down to the actual PF the same error appeared.

I have a hunch that this is due to AD still having remnants of the old server within the domain. I had to remove the previous instance of the server using ADSI edit in order to re-install Exchange in the first place so I'm kinda clutching at straws now regarding what else can be left from the old server.

Any ideas how I could get around this MAPI error?