The reason that this is classified as a paradox is that it seemingly involves communication between the two particles at speeds greater than the speed of light, which is a conflict with Einstein's theory of relativity.
The paradox was the focal point of a heated debate between Albert Einstein and Niels Bohr. Einstein was never comfortable with the quantum mechanics being developed by Bohr and his colleagues (based, ironically, on work started by Einstein). Together with his colleagues Boris Podolsky and Nathan Rosen, he developed the EPR Paradox as a way of showing that the theory was inconsistent with other known laws of physics. (Boris Podolsky was portrayed by actor Gene Saks as one of Einstein's three comedic sidekicks in the romantic comedy I.Q..) At the time, there was no real way to carry out the experiment, so it was just a thought experiment, or gedankenexperiment.
Several years later, the physicist David Bohm modified the EPR paradox example so that things were a bit clearer. (The original way the paradox was presented was kind of confusing, even to professional physicists.) In the more popular Bohm formulation, an unstable spin 0 particle decays into two different particles, Particle A and Particle B, heading in opposite directions. Because the initial particle had spin 0, the sum of the two new particle spins must equal zero. If Particle A has spin +1/2, then Particle B must have spin -1/2 (and vice versa). Again, according to the Copenhagen interpretation of quantum mechanics, until a measurement is made, neither particle has a definite state. They are both in a superposition of possible states, with an equal probability (in this case) of having positive or negative spin.
There are two key points at work here which make this troubling.
If you measure Particle A, it seems like Particle A's quantum spin gets "set" by the measurement ... but somehow Particle B also instantly "knows" what spin it is supposed to take on. To Einstein, this was a clear violation of the theory of relativity.
No one ever really questioned point 2; the controversy lay entirely with point 1. David Bohm and Albert Einstein supported an alternative approach called "hidden variables theory," which suggested that quantum mechanics was incomplete. In this viewpoint, there had to be some aspect of quantum mechanics that wasn't immediately obvious, but which needed to be added into the theory to explain this sort of non-local effect.
As an analogy, consider that you have two envelopes that contain money. You have been told that one of them contains a $5 bill and the other contains a $10 bill. If you open one envelope and it contains a $5 bill, then you know for sure that the other envelope contains the $10 bill.
The problem with this analogy is that quantum mechanics definitely doesn't appear to work this way. In the case of the money, each envelope contains a specific bill, even if I never get around to looking in them.
The uncertainty in quantum mechanics doesn't just represent a lack of our knowledge, but a fundamental lack of definite reality. Until the measurement is made, according to the Copenhagen interpretation, the particles are really in a superposition of all possible states (as in the case of the dead/alive cat in the Schroedinger's Cat thought experiment). While most physicists would have preferred to have a universe with clearer rules, no one could figure out exactly what these "hidden variables" were or how they could be incorporated into the theory in a meaningful way.
Niels Bohr and others defended the standard Copenhagen interpretation of quantum mechanics, which continued to be supported by the experimental evidence. The explanation is that the wavefunction which describes the superposition of possible quantum states exists at all points simultaneously. The spin of Particle A and spin of Particle B are not independent quantities, but are represented by the same term within the quantum physics equations. The instant the measurement on Particle A is made, the entire wavefunction collapses into a single state. In this way, there's no distant communication taking place.
The major nail in the coffin of the hidden variables theory came from the physicist John Stewart Bell, in what is known as Bell's Theorem. He developed a series of inequalities (called Bell inequalities) which represent how measurements of the spin of Particle A and Particle B would distribute if they weren't entangled. In experiment after experiment, the Bell inequalities are violated, meaning that quantum entanglement does seem to take place.
Despite this evidence to the contrary, there are still some proponents of hidden variables theory, though this is mostly among amateur physicists rather than professionals.
Second, this statement is questionable: "The explanation is that the wavefunction which describes the superposition of possible quantum states exists at all points simultaneously." This is ONE explanation. It is essentially a non-local hidden variable theory. There are other alternatives, for example that since the intrinsic spinor part of the state vector [wave function] has no spatial or temporal dependence, the collapse of the wave functions along a spin axis involves no space-time communication at all. In other words, it happens in a non space-time dimension, very different from what we ordinarily think of when we think about existence.