No such attraction happens. Let's consider two point charges of charge $q$ at rest, and say $F_{grav} = F_{EM}$.

If they are separated by a distance $d$ on the $x$-axis, the force felt by one charge from the other is

$ \vec{F}_0 = q \vec{E}_0 = \frac{kq^2}{d^2}\hat{x}$

Let's transform to a frame traveling with velocity $\vec{v} = -v_0\hat{y}$. Now the particles appear to be traveling upwards with velocity $v_0$. As you say, this induces a magnetic field---along the line separating the particles it is:

$\vec{B} = \frac{ \vec{v}}{c} \times \vec{E} = \gamma\cdot \frac{ \vec{v}}{c}\times\vec{E_0}$

where we've used the transformed $\vec{E}$-field in the new frame: $\vec{E} = \gamma\vec{E}_0$. We can calculate the Lorentz force of one particle on the other:

$\vec{F} = q\vec{E} + q\frac{\vec{v}}{c}\times\vec{B} = q\vec{E}(1-v^2/c^2) = \frac{q\vec{E}_0}{\gamma}$

since the direction of travel is perpendicular to the electric field on the diameter of the charges. This is just equal to the electric force in the rest frame scaled by a factor $1/\gamma$ due to normal frame transformations. The same such transformation will happen to the gravitational force: perpendicular to the direction of motion, it will decrease by a factor of $1/\gamma$. The forces will be equal in both frames leading to no contradiction.

If you didn't understand what I did above, then you may want to try another forum. But I can offer some less technical explanation. In moving frames, the electric field will appear to increase. This unbalances the moving charges, and would make them separate, if it were not for the attractive effect of the magnetic field. This brings them back into balance with the gravitational force. So in a slightly ironic fashion, it's the magnetic field (which you fear violates relativity) which is actually the crucial ingredient for preserving the predictions of relativity.

You can see this pdf by Kirk McDonald for a more complete derivation, and a list of classic references on this problem.