Bien,
Yo en un caso similar lo que hice fue trabajar con imagenes, y modificaba el nombre de la imagen segun el usuario que la cargaba.
Código PHP:
$archivo=explode(".", $_FILES['archivo']['name']);
$ruta = "../rrhh/imagenes/".$apellido." ".$nombre.".".$archivo[1];
copy($_FILES['archivo']['tmp_name'], $ruta);
Lo que podrias hacer es trabajar con el vector archivo, y al elemento $archivo[0] aplicarle el str_replace(' ','_',$archivo[0]);
Ya que seguramente ahi te esta generando el error.