Lo que puedes hacer es meterle un código que compruebe antes de cambiar el nombre si el supuesto nombre por el que se le canviaría ya existe (file_exists) y si existe añadirle un una serie de letras al azar...
Por ejemplo:
Código PHP:
<?php
$Nuevo = $Viejo;
$Nuevo = ereg_replace (" ", "_", $Nuevo);
if(file_exists($Nuevo)){
$rand=rand(000,999);
$Nuevo = $Nuevo . $rand;
}
rename($Viejo, $Nuevo);
Es posible que salga el rand dos veces igual, pero lo veo muy dificil, por no decir imposible, porque tiene que haber mucha casualidad para que salga el mismo nombre de archivo con el mísmo número... jeje.
Seguro que se puede hacer de otra forma sin un rand() más segura, pero solo se me ocurre esa...
EDITADO: Se me olvidó comentar que también tendrías que hacer algo para que separe la extensión del nombre del archivo. Porque sinó el nombre quedaría por ejemplo documento.doc345