You need to implement this in a custom module, here is a sample code to achieve this:

<!-- language: lang-php -->

    function custom_node_validate($node, $form) {
      if ($node->type == 'page') {
        //retrieve the value for your field using Entity API
        $wrapper = entity_metadata_wrapper('node', $node);
        $value = $wrapper->field_collection->field_unique->value();
        
        // Get field information
        $field = field_info_field('field_unique');
        $query = new EntityFieldQuery;
        $query->entityCondition('entity_type', 'field_collection_item')
          ->fieldCondition($field, 'value', $value)
          ->count();
        $count = $query->execute();
        if ($count > 1) {
          form_set_error('field_unique', 'Unique field value is already used.');
        }
      }
    }

A few disclaimers:

 - I am really stocked by the complexity of Field API and it was pretty complicated to find good information about how to retrieve values and make queries. 
 - I really enjoy doing SQL queries (see [How to change the legnth of field settings][1]) but I tried to only use the API instead of doing a simple query on the table `field_data_field_unique`. However it may not yet be perfect so please feel free to chime in.
 - The [form_set_error()][2] isn't highliting the field, I was unable to find the correct name.

Here are the documentation I used:

 - [hook_node_validate()][3]
 - [Get value of a field collection field][4] (answer from fago), the [Entity API][5] module and [entity_metadata_wrapper()][6].
 - [Checking out EntityFieldQuery][7] (by Ryan Szrama) and the [API][8].


  [1]: http://drupal.stackexchange.com/questions/8829/how-to-change-the-length-of-field-settings/10005#10005
  [2]: http://api.drupal.org/api/drupal/includes--form.inc/function/form_set_error
  [3]: http://api.drupal.org/api/drupal/modules--node--node.api.php/function/hook_node_validate/7
  [4]: http://drupal.org/node/1166238#comment-4580004
  [5]: http://drupal.org/project/entity
  [6]: http://drupalcontrib.org/api/drupal/contributions--entity--entity.module/function/entity_metadata_wrapper/7
  [7]: http://www.commerceguys.com/resources/articles/183
  [8]: http://api.drupal.org/api/drupal/includes--entity.inc/class/EntityFieldQuery/7