No te hace falta reemplazar los caracteres, con la función urlencode() reemplaza los caracteres especiales por sus correctos equivalentes para escribir en la url y así se busque el archivo correspondiente.
Código PHP:
<?
$archivo=$_GET[archivo];
if(file_exists($archivo))
{
$file=$archivo;
header("Content-Transfer-Encoding: binary");
header("Content-type: application/force-download");
header("Content-Disposition: attachment; filename=".basename($file));
header("Content-Length: ".filesize($file));
readfile(urlencode($file));
}
else
{
print "Usted esta accediendo a un archivo que no existe<br>".$archivo."<br>";
}
?>
Prueba si así te sirve ;)
Saludos.