Why can't a magnet change a charged particle's speed?

I know that magnetic force acts perpendicular to the direction of the original velocity

No, the magnetic force acts perpendicular to the current velocity. Once the direction of the velocity changes, the direction of the force changes as well.

Cast in math:

$$ m\dot{\vec v} = \vec F_L = \frac q c \vec v \times \vec B $$

From this we get ($v = |\vec v|$):

$$ \dot v = \partial_t \sqrt{\vec v^2} = \frac{\vec v \cdot \dot{\vec v}}{\sqrt{\vec v^2}} \propto \vec v \cdot (\vec v \times \vec B) = 0$$

(As $\vec v \times \vec B \perp \vec v$).