For example, if IC = 100mA and RE = 100 ohms, then gm = 100/25 = 4ma/mv (at room temperature), and gmRE = 400V/V, which is much greater than 1. The approximation works for most reasonable values of IC, but may fail at very low currents.
However, your original calculation was correct. A+