Can't set up new employees

I am trying to give a user access to set up new employees in the system.  He can create the employee record, but when he tries to fine the Person ID, he can't see it in the search window and if he just types it in and tries to save the record he gets the error "Insufficient access rights. You cannot modify Pers Protected data for the person."  The person record he is trying to use is newly created and is not set up as a protected person.  There must be some access setting I am missing.