Try to remove the address book , and then add it again.
Or try creating a new porfile in outlook and import his pst into it. To see if he gets the same message
But 1st try doing this click start and then run - type in outlook /safe
if outlook is working here without the error, he will need to uncheck the add-ins in outlook. That would be my guess is that the add-in used for this is causing the trouble.