Something to try:
On the server which houses the user’s mail file, try running nlnotes.exe. Then you can open the mail file and add admins and the user in the ACL. (by default Notes adds LocalDomainServers to the ACL of the mail file as Manager. Admins are not added by default.)
also, in the future, if you are running r5.x or above, you should be able to run the Admin client, enter the People&Groups view, People and use the Tools to recertify an individual.