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.