From what I've read, the rub is that you don't know which side of the coin the current one is until you observe it, and only at the exact time of observation does the other coin assume the other state.
Apparently, the point at which you observe the one coin is called the collapse of the wave function, and we have ways of directly measuring that the collapse doesn't happen until one of the particles is observed. (But it's never been too clear to me how that's possible... if observing a particle collapses the wave function, how do we observe when the collapse happens, without first observing the particle?)
The problem with the 'collapse' point of view is that it's easy to say "and thus only the observation we saw actually exists". But that's an extra postulate beyond asserting the wavefunction describes all of reality. By just saying the wavefunction describes all of reality, you wind up with Many-worlds: http://en.wikipedia.org/wiki/Many-worlds_interpretation So the coins/paper analogies do make sense, except that there's not a single outcome: there are two possible outcomes, both realized, but each version of you interacting ("observing" is a loaded term) with the system to the point of decoherence (http://en.wikipedia.org/wiki/Quantum_decoherence) only ever get to see one of the worlds, which is the one you find yourself in. This isn't that mysterious given that your brain and everything else in your body are made of the same fundamental particles as everything else.
You highlighted a problem with quantum computers and other things: how to make sure a system is in a quantum state without directly measuring it. It's hard to fight decoherence.
A little rusty on my QM but I believe the key to demonstrating when the collapse happens is that while doing a measurement will collapse the wave function, applying a transformation won't necessarily.
An experiment can work something like this. Produce 1000 state that you think are undecided. Apply a transformation that you know will turn the uncollapsed 50/50 state to 1 and the collapsed 0 and 1 states to the uncollapsed 50/50 state. Then measure all 1000 states. If they all yield 1, with high probability they were were indeed undecided to begin with. If they yield random results, with high probability they were collapsed 0 or 1 to begin with.
Apparently, the point at which you observe the one coin is called the collapse of the wave function, and we have ways of directly measuring that the collapse doesn't happen until one of the particles is observed. (But it's never been too clear to me how that's possible... if observing a particle collapses the wave function, how do we observe when the collapse happens, without first observing the particle?)