Se puede rootear (y cambiar el recovery) desde un recovery CWM.
Me explico.
Si tienes un recovery modificado, (cosa que dudo si es que lo has hecho con el KIES...) tendrás un "MOUNTS AND STORAGE". Desde ahi, conectas el terminal al PC, y ya podrás meterle lo que quieras para después instalarlo desde "Install ZIP from SDcard".
Pero, si te deja entrar en modo Download, y el Odin te lo detecta, flashea con el Odin, y nunca más uses el Kies para actualizar el terminal, pues siempre pasan mierdas por este estilo.