Mediante explode puedes obtener el nombre del archivo y la extensión. Después le puedes añadir un nombre único usando, por ejemplo, la función time:
Código PHP:
//Fichero de entrada ejemplo1.jpg
$n_aux = explode (".", $_FILES["imagen"]['name']);
$nombre = $n_aux[0] . "_" . time() . "." . $n_aux[1];
//nombre = ejemplo1_193989423.jpg
Y subes ese fichero