Error updating certifier ID

When I try to make a cross certify between to Organizational ID’s (X and Y) I get the following error on one (X) of them:

"Error updating certifier ID

The following error occured while trying to update the certificates stored in the Certifier ID with those from the directory on the server you selected:

The encrypted data has been modified or the wrong key was used to decrypt it

Do you wish to continue without updating the Certifier ID?"

Here you are presented with YES or NO option.

I have compared the public keys between the ID file itself and the one stored in the Domino Directory, they both match up.

The root to this we believe is that a new certifier was created for organization X when the one in use was about to expire. The user who created this ID got a question if he wanted to update with the new ID at which he answered yes.

Could the update of with the new ID info have been stalled somewhere or is there some other solution to this issue?

Many thanks for response on this matter!