There is no fallacy, you're just not being particularly careful. You need to include both the electric and magnetic forces of the right magnitude and a covariant result drops out.
(Of course historically it went the other way around: people noticed that frame changes were messed up unless the transformation laws were different and this led to the development of special relativity.)
For simplicity let both beams be very thin and have equal uniform charge density $\rho$ in the rest frame and suppose they run exactly parallel separated by a distance $l$. Let the velocity of the beams be $v$ in the lab frame.
Rest frame:
Taking the usual gaussian pillbox gives the electric field of one beam at the location of the other as
$$ \vec{E}_\text{rest} = \frac{\rho}{2\pi\epsilon_0 l} \hat{r}, $$
where $\hat{r}$ is the unit vector directed away from the source beam. Thus the force on a single particle in the second beam (charge $q$) is:
$$ \vec{F}_\text{rest} = \frac{\mathrm{d}p}{\mathrm{d}t_\text{rest}} = \frac{\rho q}{2\pi\epsilon_0 l} \hat{r}. $$
Lab frame:
The charge density of the beam is enhanced by the relativistic $\gamma=1/\sqrt{1-v^2/c^2}$ factor. Thus the electric field is:
$$ \vec{E}_\text{lab} = \frac{\gamma \rho}{2\pi\epsilon_0 l} \hat{r}. $$
There is also a magnetic field of magnitude
$$ B = \frac{\mu_0 \gamma\rho v}{2\pi l} $$
and directed so as to produce an attractive force. Plugging these in the Lorentz force formula
$$ \vec{F}_\text{lab} = q (\vec{E}_\text{lab} + \vec{v}\times\vec{B}) = q\left( \frac{\gamma \rho}{2\pi\epsilon_0 l} - \frac{\mu_0 \gamma\rho v^2}{2\pi l}\right) \hat{r} = \frac{\rho q}{2\pi\epsilon_0 l}\gamma\left(1 - \epsilon_0\mu_0 v^2\right) \hat{r}. $$
Using $\epsilon_0 \mu_0 = c^{-2}$ this reduces to $\vec{F}_\text{lab} = \gamma^{-1} \vec{F}_\text{rest}$ which, on noting the relativistic time dilation $\mathrm{d}t_\text{lab} = \gamma \mathrm{d}t_\text{rest}$, is exactly right! Note that I've used the fact that the force is orthogonal to the velocity implicity when writing the Lorentz transformation law for the force. You can prove the covariance for general motions using the covariant formulation of EM.
Lesson:
Relativity and electromagnetism go together like hand and glove!
The force is given by:
$$ \vec F = I \oint_{\gamma_2} d\vec r \times \vec B(\vec r).$$
Where $\vec B(\vec r)$ is the field generated by coil 1 and $I$ is the current in coil 2 and the integral is along the curve $\gamma$ which is described by the wires of the coil 2. Note, that there might also be a torque.
Knowing the maximal or homogeneous field $B$ in the interior of the coils does not help much.
The field of the coil is given by the Biot-Savart law:
$$ \vec B(\vec r) = \frac{\mu_0 I}{4\pi} \int_{\gamma_1} \frac{d\vec r' \times (\vec r - \vec r')}{\left| \vec r - \vec r' \right|^3}.$$
Also note, that levitating a stationary magnet in a stationary magnetic field is always unstable due to the Earnshaw theorem. You will have to use some form of regulation to keep the system stable. Calculating some fixed parameters will not help you (but might help in the design of the system).
Best Answer
Qualitatively:
Very close, electron clouds try to overlap, resulting in a repulsive electrostatic force.
In the medium distance, the polarity of the electron cloud distribution means that there is some configuration in which a molecule can line up net positive charge to net negative charge, resulting in an attractive electrostatic force between neutral molecules.
The farther apart the molecules are, the more they just look like neutral points, instead of distributed net neutral charge arrangements.