We study the linear stability of a planar interface separating two fluids in relative motion, focusing on conditions appropriate for the boundaries of relativistic jets. The jet is magnetically dominated, whereas the ambient wind is gas-pressure dominated. We derive the most general form of the dispersion relation and provide an analytical approximation of its solution for an ambient sound speed much smaller than the jet Alfv\'en speed $v_A$, as appropriate for realistic systems. The stability properties are chiefly determined by the angle $\psi$ between the wavevector and the jet magnetic field. For $\psi=\pi/2$, magnetic tension plays no role, and our solution resembles the one of a gas-pressure dominated jet. Here, only sub-Alfv\'enic jets are unstable ($0Comment: 9 pages, 6 figures, submitted to journal