I tried:

$args = array(
  'access_token' => $access_token,
  'id' => $uid
);

$url = "https://graph.facebook.com/{$idPhoto}/tags";

$ch = curl_init();
curl_setopt($ch, CURLOPT_URL, $url);
curl_setopt($ch, CURLOPT_HEADER, false);
curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);
curl_setopt($ch, CURLOPT_POST, true);
curl_setopt($ch, CURLOPT_POSTFIELDS, $args);
curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, false);
curl_setopt($ch, CURLOPT_SSL_VERIFYHOST, 2);
$data = curl_exec($ch);

It has returned me:

{"error":{"type":"QueryParseException","message":"Unknown path components: \/tags"}}

It does not seem possible because its not in the Facebook documentation:

http://developers.facebook.com/docs/api#publishing

Can someone confirm me that it's not possible to tag a user in a recently uploaded photo?