an example where changing the frame of reference of an observer changes the outcome of events! consider two  identical charges moving with uniform velocity. There will be a magnetic force of attraction between them as two currents in the same direction attract each other. If I sit on one of the charges, according to me the other charge is not moving. So there wont be any magnetic attraction. How does changing the frame of reference change the outcome of the interaction? What is it that will actually happen?
 A: You're right; in the frame moving with the charges there will be no magnetic attraction. There will however be an electrostatic repulsion, so you will see the two particles move away from each other.
Consider another frame (the rest frame) where both particles move side by side in the x direction (I assume this is what you are imagining). The particles still repel each other electrostatically, but now they attract one another magnetically as well!
This may seem like a problem, but it isn't because even though the force measured in the rest frame is weaker since the electrostatic repulsion is partially canceled by the magnetic attraction, the time experienced by moving observers is also different due to the witchcraft of special relativity. If the frame moving with the charges is primed, and the rest frame is unprimed, then
\begin{align} t^\prime &= \gamma t \\ F &= q(E + v\times B) = q(E - vB) \\ F^\prime &= qE^\prime \end{align}
What we seek to show is that since force is inversely proportional to the square of the time, F and F' are related by a factor of $\gamma^2$ in which case observers in either frame will calculate matching trajectories using Maxwell's equations.
Since for a point charge
$$ E = \frac{1}{4\pi\epsilon}\frac{q}{r^2} $$
$$ B = \frac{\mu}{4\pi}\frac{qv\times\hat{r}}{r^2} = \frac{\mu}{4\pi}\frac{qv}{r^2}$$
Now we have all we need. Plugging B in to F and using $ \mu = 1/(c^2\epsilon) $ and $ \gamma = 1/\sqrt{1-\frac{v^2}{c^2}} $
$$ F = q(E - vB) = q\left(E - \frac{v^2}{c^2}\frac{1}{4\pi\epsilon}\frac{q}{r^2}\right) = q\gamma^2E$$
$$ F^\prime = qE^\prime = qE = \frac{1}{\gamma^2}F $$
Which is what we wanted all along since
$$ F = \frac{\mathrm d^2y^\prime}{{\mathrm dt^\prime}^2} = \frac{\mathrm d^2y}{(\gamma ~\mathrm dt)^2} = \frac{1}{\gamma^2}F $$
(noting that dy is unaffected by a boost in the x direction)
To solve more complicated problems of this sort, you usually want to talk about faraday tensors, 4-currents, and einstein notation, but I hope this simple example gave you some insight into how electromagnetism and special relativity are related. You may have wondered what if the particles go so fast that the magnetic force exceeds the electrostatic repulsion, but indeed you can see that to do so you must exceed the speed of light!
If you want to understand why electromagnetism is manifestly robust against relativity paradoxes, you'll want to learn about tensor analysis in 4D spacetime, which is must-know knowledge for any physicist worth his salt and can be found in the back of most mechanics or electrodynamics textbooks or in the beginning of most general relativity books. If you want to gain some physical intuition for how EM works I recommend Purcell simplified.
http://physics.weber.edu/schroeder/mrr/MRRtalk.html
A: In Feynamn lectures, he shows in a rather straight-forward manner, taking the example of a charge moving parallel to a wire, that a complete electromagnetic description is invariant to the inertial frame of reference, i.e. electricity and magnetism taken together are consistent with Einstein’s relativity. 
So in cases, such as your example, you must always keep in mind how the mixture of the electric $\mathbf{E}$ and magnetic $\mathbf{B}$ fields changes from one observer to another. Some quotes from his book: 

It turns out that any inertial frame will do. We will also see that
  magnetism and electricity are not independent things—that they should
  always be taken together as one complete electromagnetic field.
  Although in the static case Maxwell’s equations separate into two
  distinct pairs, one pair for electricity and one pair for magnetism,
  with no apparent connection between the two fields, nevertheless, in
  nature itself there is a very intimate relationship between them that
  arises from the principle of relativity. Historically, the principle
  of relativity was discovered after Maxwell’s equations. It was, in
  fact, the study of electricity and magnetism which led ultimately to
  Einstein’s discovery of his principle of relativity.

One example of relativistic factors coming into play, using the laws of electromagnetism, before special relativity, can be found here, if you're interested.
Further on in his derivation you will see that charge densities are also frame dependent, for the total charge conservation law to hold. Neat!
To cut to the final result:

We have found that we get the same physical result whether we analyze
  the motion of a particle moving along a wire in a coordinate system at
  rest with respect to the wire, or in a system at rest with respect to
  the particle. In the first instance, the force was purely “magnetic,”
  in the second, it was purely “electric.

I started off with Feynman's example, just to set some context, now back to our case, without wire, as Luboš pointed out in comments, in the frame of reference of the moving charges, there's just the Coulomb repulsion between the two protons (or two electrons), whereas in the laboratory's frame (moving charges) the Coulomb repulsion is coupled with a magnetic force attracting the two. Following the reasoning presented earlier, the electric & magnetic field transition between the two frames mentioned, is simply obtained by applying the Lorentz transformations on the fields of one frame to obtain the other. Here for our specific problem, we can just work with the transversal components of $\mathbf{E}$, denoted as $E_t$. 
In the rest frame of charges, $S$, we have only an electric field, its traversal component denoted $E_t$, the Lorentz transform giving the transversal electric field in $S'$ is: 
$$E'_t = \gamma(E_t-|\vec{v}\times \vec{B}|)$$
Note the appearance of a magnetic field in the expression!
Now having defined the fields in both frames, we know the charges will be subject to EM forces in each frame, so in order to check the physics, let's find out what the transverse momenta of each the charges are, after the EM force has acted on them for a certain time. We expect the results to be the same in both frames.
Employing the correct relativistic equation of motion $\mathbf{F}=d\mathbf{p}/dt$, after the time interval $\Delta t$ we expect the transverse momentum change to be $\Delta p_t=F\Delta t$ in $S$, and $\Delta p'_t=F'\Delta t'$ in $S'$.
Obtaining the same result of the transverse momentum change in both frames, means the following relation should hold:
 $$\frac{\Delta p_t}{\Delta p'_t}=1=\frac{F \Delta t}{ F' \Delta t'}$$
Where for any chosen time interval $\Delta t$ in $S$, the corresponding time interval in $S'$ is dilated (time dilation in moving frames): $$\Delta t'=\gamma \Delta t$$
Now we just have to find the expression of $F'$, the expected result should cancel out the effect of the time dilation, for the momentum in the transverse direction to be conserved. We know that in $S'$ each charge is also subject to a magnetic field, and its effect should reduce the Coulomb's repulsion. Knowing $E'_t$ (from earlier), we have the total EM force on each charge in $S'$ is given by: $$
\begin{align}
F'=\gamma q (E_t - vB)&=\gamma q \left(E_t-v\left(v\frac{E_t}{c^2}\right)\right) \\
F'&=\gamma q E_t\left(1-\frac{v^2}{c^2}\right)
\end{align}
$$
Substituting $\Delta t'$ and $F'_t$ by the above expressions, we obtain: $$\frac{F \Delta t}{ F' \Delta t'}=\frac{F \Delta t}{\gamma^2 (1-\frac{v^2}{c^2}) F \Delta t}=1$$
Which is indeed equal to 1, as $\gamma=(1-v^2/c^2)^{-1/2}.$
Hence the same physical result is obtained from either frame of reference, $S$ and $S'$, no paradox! To conclude, a quote from Feynman again: 

A complete electromagnetic description is invariant; electricity and
  magnetism taken together are consistent with Einstein’s relativity.

Further useful readings: 
Feynman lectures, Vol II chapter 13-6.
Lorentz transformation of the fields
Lorentz transformation for EM, from wikipedia.
