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.
But the row of moving electrons is contracted in the lab frame, compared to what the cat sees. You can see that in your screencaps from the video too -- Derek sees 10 electrons per image width, whereas in the rest frame of the electrons there are only about 8½ electrons per image width.
What is potentially confusing is that as far as the electrons themselves are aware (electrons are not "aware" of anything, but never mind), they are not that the same mutual distance when they are moving as when the wire carried no current.
In other words, the row of electrons is not a rigid object. If each pair of neighboring electrons had been separated by a little rigid rod, the electrons would have to come closer together when the current starts flowing. But there are no such rods, and the row of electrons is free to stretch when the current begins to flow, and this stretching is exactly canceled out by the length contraction, such that in the lab it looks like the distance between the moving electrons is the same as the distance between the stationary protons.
What does the cat see? When the wire didn't carry current, the electrons and protons moved backwards together at the same speed (and with the same contracted spacing as the cat sees the protons have during the entire experiment). Then, when the current starts to flow, the electrons in front of the cat begin coming to a halt (with respect to the cat) slightly before those behind it. So from the cat's point of view the row of electrons get significantly stretched.
Meanwhile, Derek will see all the electrons begin to move at the same time. The cat and Derek do not agree whether two electrons changed their velocity at the same time or not -- this is relativity of simultaneity and is mathematically necessary to make length contraction consistent.
Best Answer
Whoever the PRL referee(s) was/were, they should have sent it back to the author to put the argument into a manifestly covariant formalism. The editors should have done the same before the paper got to a referee. As it is, everybody has to waste time unpicking the 3-d vector mess. 3-d vectors have a perfectly legitimate place in Physics, but not if one is constructing arguments concerning Lorentz invariance/covariance or otherwise.
The title is misleading on the face of it, because the problem is reported as a failure of the system to conserve momentum, which is associated with translation invariance, not with Lorentz invariance.
There is only a "problem" if one is using the macroscopic form of Maxwell's equations. If one is using the macroscopic equations, the system will not be translation invariant if the material background is not homogeneous, similarly for rotation invariance and isotropy. If the background material is not homogeneous (and isotropic), momentum (and angular momentum) will not be a conserved quantities. Introducing the Einstein-Laub formula as a way to jury rig a non-covariant formalism is significantly too ad-hoc.
In any case, if a manifestly Lorentz and translation invariant Lagrangian can be constructed for a model, the forces that act in that model can be presented in a manifestly covariant way. The force equations could be arbitrarily complex, depending on what Lagrangian we introduce. The Einstein-Laub force law can only be applicable in a restricted setting, just as the Lorentz law is. One comment on the Science article linked to in comments points to a more-or-less intuitive resolution, "So what is wrong with polarization and magnetization being fundamental, given that point particles carry angular momentum and the quantum vacuum can be polarized?" Ultimately, this would have to be cashed out with a Lorentz and translation invariant Lagrangian (and then it would have to be quantized, etc.), but this seems the most positive thing to take from the paper. A panoply of Lorentz and translation invariant equations could be written down that include the displacement and the magnetic induction as well as the electric field and the magnetic field as dynamical degrees of freedom, though proving anything about any given system might be prohibitively difficult.
A lot more could be said, and I have a feeling more will be said because the paper has been linked to across the web, by ZapperZ, for example, on May 3rd. Now that the paper has been published, it's fair game. It's different enough from what most people are doing in Mathematical Physics, however, that relatively few people will care much. Anyone who is busy with their own research is unlikely to comment, unless, like me, they're cross enough. I've now commented on this paper twice (at ZapperZ long ago), however, so it's time to join the ranks of people who are ignoring it.
EDIT(5/24/2012): ZapperZ has added two postscripts about new rebuttals on arXiv.