Puedes usar la siguiente funcion:
  Código PHP:
    function no_sobreescribe($nom_imagen, $carpeta) { 
$separador = "_"; 
$sin_separador = ereg_replace($separador, "_", $nom_imagen); 
if ( !file_exists($carpeta.$sin_separador) ) { 
  $nombre_correcto = $sin_separador; 
  } 
 else { 
  $nombre_temp = $sin_separador; 
  $nombre_sep = $separador.$nombre_temp; 
  $i = 0; 
  while ( file_exists($carpeta.$nombre_temp) ) { 
   $nombre_temp = $i.$nombre_sep; 
   $i++; 
   } 
  $nombre_correcto = $nombre_temp; 
  }
 return $nombre_correcto; 
 } 
    
  Esta funcion se usa de la siguiente manera:  
 Código PHP:
    $carpeta="la/ruta/del/la/carpeta";
$nombre=no_sobreescribe($_FILE["archivo"]["name"],$carpeta);
//y asi ya tienes un nombre de archivo que no se repite