Thanks for asking an interesting question! One way to think about the answer is using special relativity. In short, the particle itself sees the magnetic field in, (say the z direction), in our stationary frame transformed into an electric field in the -y direction in its moving frame. This electric field has the correct magnitude to create a force on the charge equal to the Lorentz force from the magnetic field in our frame. Just as time and space are actually each part of space-time and transform between each other as the velocity between the moving and laboratory frames change, the electric and magnetic fields are part of the electromagnetic field and transform in a similar manner.
For a frame, $S^{\prime}$, moving with our charged particle along the x axis with respect to electric, $E$, and magnetic $H$ fields in the laboratory frame, Karapetoff[1][2] gives the following Lorentz transform for the $E'$ and $H'$ fields.
$E_y' = E_y cosh\left(u\right)-H_z sinh\left(u\right)$,
$H_y' = H_y cosh\left(u\right)-E_z sinh\left(u\right)$,
$E_z' = E_z cosh\left(u\right)-H_y sinh\left(u\right)$, and
$H_z' = H_z cosh\left(u\right)-E_y sinh\left(u\right)$,
where $u$ is the rapidity of the frame that moves with the particle. As a matter of reference, u can be expressed as
$v/c = tanh\left(u\right)$,
where v is the speed of the particle in the laboratory frame, but we won't make use of this.
There are a few interesting things to note here. First, the $E$ and $H$ fields transform via a rotation matrix in a hyperbolic space. Second, there's an interesting contrast to the Lorentz transform for space-time. Whereas in space-time only lengths parallel to the direction of motion are changed, when the electromagnetic field is Lorentz transformed, only quantities perpendicular to the direction of motion are changed.
Getting back to the original question, "Why does the magnetic force act at right angles to the magnetic field", let's look at what the moving particle sees in its own frame, S'. Due to the Lorentz transform shown above, in the $S'$ frame, there is now an electric field in the y direction.
$E_y' = E_y cosh\left(u\right)-H_z sinh\left(u\right)$,
but $E_y$ in the laboratory frame is zero so
$E_y' = -H_z sinh\left(u\right)$
There is still an $H$ field in the z direction equal to $H_z cosh\left(u\right)$. This threw me for a bit, because I was worried about the Lorentz force due to this field. There is however no need for concern. Since we're in the frame of the moving charged particle, its relative velocity is zero. Consequently the magnetic field produces no force in this frame.
Now we'll use the formula
$sinh\left(u\right) = \frac{v}{\sqrt{1-v^2/c^2}} = v\gamma$
to get,
$E_y' = -H_z v\gamma$
We're interested in the force on the particle, $F=qE_y'$, so we write down
$E_y' q = -q H_z v\gamma$
This is starting to look pretty good. The E field producing a force on the moving charged particle is proportional to the magnetic field times the velocity of the particle. There's still one problem. We have a $\gamma$ in the expression which doesn't show up in the Lorentz force law. Force can also be expressed as $F=ma$. Since we're working in special relativity, however, we need to express the (transverse in this case) force using relativistic mass so we get $F=\gamma m a$. This finally gives us
$F = \gamma m a = -q H_z v\gamma$
The $\gamma$'s cancel out to give the correct answer for the magnitude of the force:
$F = -qH_zv$. In this case, however, the force was created by an electric field in the same direction.
There's one last interesting thing to note here, at least for my purposes. The force acting in a direction perpendicular to the motion of the charged particle doesn't need to be adjusted for special relativity. There are no factors of $v/c$ in the final, exact, (as opposed to a low speed approximation), answer.
References
Karapetoff, V., "Restricted Theory of Relativity in Terms of Hyperbolic Functions of Rapidities", American Mathematical Monthly, 43, (1936), 70
Karapetoff, V., "TRANSFORMATION OF ELECTRIC AND MAGNETIC FORCES IN A PLANE WAVE, IN A PLANE NORMAL TO THE DIRECTION OF RELATIVE MOTION OF TWO OBSERVERS", Physical Review 23, (1924), 239