Magnetic force on a charged particle viewed from 2 inertial frames

The resolution to this paradox is that the electric and magnetic fields need to be transformed when you change from one inertial frame to another, through rules fixed by special relativity. This is explained in this Wikipedia page or in your favourite EM textbook's relativity section, but the short of it is that in the frame transformation you describe, the magnetic field is tranformed into an electric field given by $$ \mathbf E'= \gamma \, \mathbf u \times\mathbf B, $$ where $\mathbf u$ is the velocity of the new frame with respect to the old one and $\gamma = 1/\sqrt{1-u^2/c^2}$. This new electric field acts on the particle to fully cancel out the effect of the magnetic force it feels on the new frame - electric and magnetic fields change from one inertial frame to the next, but if the total force is zero in one frame it must be zero in all frames.

It can feel pretty funny that one needs to invoke relativity to deal with what was originally a galilean reference-frame transformation, but that's just the way the cookie crumbles: electromagnetism was a fully relativistic theory from the time Maxwell formulated it, and in fact it was precisely these sorts of symmetries in electromagnetic analyses from different reference frames that motivated Einstein to develop special relativity.