I really don't know the exact historical chain of events, so I might even give a result that popped up after SR came into existence. In fact, I figured out two different ways of explaining this, which I've given here. The first one is IMHO classical, but the fact that Coulomb's law is only for static cases may be incorrect in classical physics. I doubt it, though; Maxwell knew the relation of EM fields with EM waves. The second explanation makes sense from a pure classical POV, before Maxwell. They conflict each other, though they both explain it. So I'm giving both here. Comments appreciated on which is more correct.
I'm referring to electric field as E and magnetic field as B here, with standard notations.
Answer #1
In classical mechanics, you can solve this by changing the definitions of electric and magnetic fields. They're the same thing. Moving with a velocity makes an E field into a B field or vice versa. Aside from that, Coulomb's law is only applicable for electro-static situations. When the particle is moving, the E field is different.
In the end, only force has to be the same in inertial frames. If E became B on a change of velocity, the formulae will be such that the force stays the same. An observer travelling along with the moving particles will see an E, no B, whereas an observer at "rest" (basically moving relative to the particles) will see a B field and a smaller E field. But, both observers will feel the same force, and they will see the particles being attracted/repelled by the same amount.
One way to look at this is from the fact that EM fields are transmitted/mediated by EM radiation. So, going at a velocity changes the behaviour of the waves in your frame.
Actually, I had this confusion a few years ago (for two parallel particles) I assumed electrostatic force in both cases, and got some strange results. Knowing that SR had its origin somewhere in electromagnetism, I assumed an unknown length contraction and resolved it. Surprisingly, the lorentz factor popped up in my equations (since $\mu_0\epsilon_0=1/c^2$ except that the length contraction was in the perpendicular direction. This is all the result of using electrostatic force in both cases.
Note that the shift in fiels is pretty tiny for nonrelativistic cases, owing to the $c^2$.
For your first case, the problem becomes trivial after this. In your frame, a bit of the magnetic field lines are electric field lines. Problem solved.
In fact, one can look at a magnetic field as a sort of 'reserve E field'. When a particle moves through a magnetic field, in its frame, it sees itself at rest. So the force it feels is an electric field, which was 'drawn from' the 'reserve E field' (i.e., the magnetic field). One can look at it the other way around as well, though not
Answer #2
Remember, in classical mechanics, we do have the lumineferous aether, which acts as an absolute reference frame for light. So even in classical mechanics, wierd things do happen when going near-lightspeeds. Your reference frames are no longer equivalent, anyways. Since EM fields are transmitted by em waves, the aether playe a crucial part. At near lightspeeds, $\mu_0\epsilon_0=1/c^2$ becomes significant in your equations.
