We study the effects of rotation on the torsional modes of oscillating relativistic stars with a solid crust. Earlier works in Newtonian theory provided estimates of the rotational corrections for the torsional modes and suggested that they should become CFS unstable, even for quite low rotation rates. In this work, we study the effect of rotation in the context of general relativity using elasticity theory and in the slow-rotation approximation. We find that the Newtonian picture does not change considerably. The inclusion of relativistic effects leads only to quantitative corrections. The degeneracy of modes for different values of m is removed, and modes with l=m are shifted towards zero frequencies and become secularly unstable at stellar rotational frequencies ~20-30 Hz.