Cierto, todas las roms vienen rooteadas. Lo que le pide es actualizar el binario desde la aplicacion, suele ser habitual en dicha aplicacion si el binario es viejo. Aunque si no recuerdo mal de mi ultima CM estas vienen o venian con superuser, no supersu...
karlrock, asegurate de que no tienes superuser instalado, podria ser el problema. Si no es asi cuando le des a continuar te deberia dar dos opciones, la normal y otra por recovery (no recuerdo si pone recovery o cwm/twrp). Supongo que la que te falla es la normal, prueba con la otra opcion.