El espacio NO debe ir, ese detalle se me escapó en mi primer respuesta (de hecho contesté sin leer completamente)
La razón por la que te da error quitarle el espacio es que te queda \$, que se interpreta como $ literalmente, sin cambiar por el valor de la variable.
Es decir, la cadena queda como
"C:\Mis documentos\Mis imágenes$nombre_archivo"
y "C:\AppServ\www\secretaria\imagenes$foto"
pero sin cambiar la variable por su valor.
No es esa la única forma de concatenar una cadena con una variable, de hecho la forma más rápida es hacerlo así:
Código PHP:
rename('C:\Mis documentos\Mis imágenes\'.$nombre_archivo, 'C:AppServwwwsecretariaimagenes.$foto)
(comillas simples delimitando la cadena, y el punto para unirla con la variable)
Probá a ver si ahora sirve.
Saludos.