If this is for a Contact record, check that the following are true:
  1. The External_Id__c field for Contact records must be set to Unique.
  2. Permissions for the Integration User must include "View All" on the Contacts object.
  3. Permissions for the Integration User must also be set to "View All Data."

If any of the above are not true, change them, then rebuild the Queue Problem Management errors.