Bueno, despues de días buscando ya encontre la solución. Resulta que encontre esta pagina
http://support.microsoft.com/es-es/kb/811528 donde dice:
Cmd.exe reconoce archivos con las extensiones .com, .exe, .bat, .cmd, .vbs, .js y .ws, así como cualquier otra extensión definida como archivo ejecutable por la variable de entorno PATHEXT, pero también puede ejecutar archivos sin estas conexiones conocidas si la imagen binaria del archivo contiene un encabezado ejecutable.
Asi que agregue .exe a PATHEXT y ya funciona la consola correctamente.
Al parecer fue alguna instalación de ruby la que desconfiguro esto porque la variable ya tenia esto:
%PATHEXT%;.RB;.RBW;
Al menos ya quedo, y espero le sirva a alguien mas.
Saludos