This should be on physics.SE, but here goes:

In the lab frame, each electron moves in the other electron's magnetic field, which creates a magnetic attraction between them. Thus, they will be seen to move away from each other _slower_ than their Coulomb repulsion would dictate. (Note, incidentally, that the "Coulomb replusion" wouldn't be the entire story anyway -- the instantaneous _electric_ field of a moving charge differs from the field of a stationary charge at the same place).

In the (initial) rest frame of the electrons, there is no magnetic force, only the Coulomb repulsion, so the electrons move away from each other _faster_ than in the lab frame.

How to reconcile those two computations? Relativistic **time dilation** comes to the rescue -- the slow separation we see in the lab frame is exactly the fast rest-frame separation, slowed down by the relativistic gamma factor.

Lesson to take home: The net _force_ on each electron is not invariant between frames of reference -- but the entire electomagnetic theory gives consistent answers about the actual _movement_ of charges when calculations are done in different inertial frames.

---

By the way, note that classical electromagnetism is not only "still quite good"; it fits _perfectly_ across _all_ speeds up to $c$, since it happens to be invariant under Lorentz transformations (provided that the fields are transformed accordingly) even though it was formulated before relativity.