Debes utilizar el código de páginas ANSI adecuado para el tipo de set de caracteres que vayas a utilizar...

http://en.wikipedia.org/wiki/Windows-1252

@Echo OFF & CHCP 1252 1>NUL
 
Rename "ñaña.txt" "ñeñe.txt"
 
Pause&Exit

Además de eso asegúrate de guardar el script con codificación ANSI, no UTF/Unicode. Si no usas un editor de texto de terceros entonces ANSI es la codificación predeterminada por el notepad)

Saludos.

Si, si quieres usar el set de caracteres Hispano tienes que especificar el CHCP Hispano, en todos y cada uno de los códigos donde uses dichas letras, y además guardar los archivos en codificación ANSI de Windows.

Hay otras alternativas, como especificar el CHCP por defecto que debe usar la consola de tu sistema operativo (lo puedes hacer desde el registro), o hacer la conversión manual de la letra "ñ"/"¤" (lo que estabas haciendo y no te funcionaba, porque tienes los archivos en UTF), si haces esto último entonces no requieres usar el comando CHCP.

El comando CHCP cambia la manera en la que se interpretan algunas letras, o mejor dicho adapta la interpretación de un set de caracteres específico para una región en concreto.

Lee: http://en.wikipedia.org/wiki/Code_page + http://ss64.com/nt/chcp.html

Saludos