Class name must be a valid object or a string

If $matched_entities is not set, and $flag == FALSE, We still need to set_error().
Maybe we could fix it in this way:

if ($flag) {
      $query = new EntityFieldQuery();
      if ($scope == 'global') {
      }
      elseif ($scope == 'entity') {
        $query->entityCondition('entity_type', $this->rule->entity_type);
      }
      elseif ($scope == 'bundle') {
        $query->entityCondition('entity_type', $this->rule->entity_type);
        $query->entityCondition('bundle', $this->rule->bundle);
      }

      list($id, $vid, $bundle) = entity_extract_ids($this->rule->entity_type, $this->entity);
      if ($this->rule->entity_type == 'user' && arg(0) =='user' && arg(2) =='edit' && empty($id)) {
        $id = arg(1);
      }
      if ($this->rule->entity_type == 'field_collection_item' && arg(0) == 'field-collection' && arg(3) =='edit' && empty($id)) {
        $id = arg(2); 
      }
      if ($this->rule->entity_type == 'profile2' && empty($id)) {
        $arg_index = 1;
        if (module_exists('profile2_page')) {
          $profile_type = profile2_type_load($this->entity->type);
          $path = profile2_page_get_base_path($profile_type);
          $arg_index = count(explode('/', $path));
        }
        $uid = arg($arg_index);
        if (arg($arg_index + 1) == 'edit' && is_numeric($uid) && $account = user_load($uid)) {
          if ($profile = profile2_load_by_user($account, $this->entity->type)) {
            $id = $profile->pid;
          }
        }
      }
      if (!empty($id)) {
        $query->entityCondition('entity_id', $id, '!=');
      }
      //Always bypass all access checkings.
      $query->addMetaData('account', user_load(1));
      $query->fieldCondition($this->rule->field_name, $this->rule->col, $this->value);

      // Store a copy of our matched entities for our use in tokens later.
      $matched_entities = $query->execute();

      $count = $query
        ->count()
        ->execute();
      if ($count) {
        $flag = FALSE;
     $token = array(
        '[count]' => $count,
      );
      // Find the first entity that failed this unique condition so we can
      // add a token referencing it. First, we have some special handling for
      // field collection entities so we can find the entity title of
      // whatever the specific field is connected to.
      $entity_types = array_keys($matched_entities);
      $entity_type = reset($entity_types);
      $matched_entity = reset($matched_entities);
      $first_match = reset($matched_entity);
      $entity_info = entity_get_info($entity_type);
      $entity_key_id = $entity_info['entity keys']['id'];
      $entitys = entity_load($entity_type, array($first_match->{$entity_key_id}));
      $entity = reset($entitys);

      if ($entity_type == 'field_collection_item') {
        $host_type = $entity->hostEntityType();
        $host_entity = $entity->hostEntity();
        $label = entity_label($host_type, $host_entity);
        $uri = entity_uri($host_type, $host_entity);
      }
      else {
        $label = entity_label($entity_type, $entity);
        $uri = entity_uri($entity_type, $entity);
      }

      $token['[existing-entity-label]'] = $label;
      $token['[existing-entity-link]'] = l($label, $uri['path'], $uri['options']);
      }

    }

    if (!$flag) {



      $this->set_error($token);
    }

@Chi, #1 didn't work for me. It did get rid of the error message, but then the validation itself no longer works (although I was never able to check if this specific validation even works in the first place due to the initial error message).

@g089h515r806, where do I apply #3?

P.S. Here's how I was able to reproduce this error message (TL;DR):

1) Use this module with Entity Reference.
2) Create an entity reference field and set a "Unique values" validation at /admin/structure/types/manage/CONTENT_TYPE/fields/ENTITY_REFERENCE_FIELD/validation.
3) Try creating a duplicate entity reference.