EPR Paradox: What's paradoxical about it?

The EPR Paradox is the one where two particles go lightyears apart from each other, and when someone observes one and sees that it's positive, it turns out that the other one is negative. And the physicist is like: "Spooky! How did the other one know to be the opposite?" And you're like: "Uh.. they chose to be that way to begin with?"

But the setup isn't quite that simple. It's more like this:

Imagine an old box maker makes two boxes. Each box has three buttons on top: a red button, a green button and a blue button. Pressing a button opens the box, revealing a coin. The coin might be heads up or tails up.

The box maker claims that the first time the boxes are opened, the following is true: if one box is opened by pressing the red button and the other box is opened by pressing the blue button, then the coin sides will be different — one heads and one tails. Otherwise, the coin sides will be the same. This is true even if the boxes are first opened lightyears apart from each other.

If you can explain how the boxes work without faster-than-light communication, then you have "solved" the EPR Paradox.

update: Another thing worth pointing out is that although faster-than-light communication appears to take place in this setup, this does not imply that the boxes can be used to actually communicate anything. I didn't say this above, but an extra claim about the boxes is that the first box to be opened, no matter how it is opened, has a 50% chance of showing heads or tails.

Hence, the second box to be opened, in the absence of knowledge about what happened with the first box, also appears to have a 50% chance of showing heads or tails. It is only when the box openers get together later and compare their results that they'll notice that their coins are the same or different according to which buttons they both pressed.