Can Not Recertify Person after upgrade to Domino 8.5

I am getting the following error while trying to Recertify any Person :

Admin Process: Received the following error performing a Recertify Person in Domino Directory request on somename/mydomain (File name: names.nsf; Name: somename/mydomain): User name not found in Domino Directory

The request get stuck and is never accomplished.

Before the upgrade it worked fine!.

Please help, thanks a lot.