The thing with black holes is that they have the same gravitational pull as the star that forms it. Yeah, it'd suck if Earth collided with a black hole, but it'd also suck if we collided with a star, and as far as I can tell there are a lot more stars than black holes.

If you have two entangled qubits separated by a large distance, and you make a measurement on one qubit, the state of the other qubit will change instantaneously. That is to say, the quantum information associated with both of the qubits will change instantaneously over a large distance. You're right in saying that "no actual information is conveyed by that change," if by information you mean classical information-- you certainly couldn't send a message faster than the speed of light. But quantum information is a very different concept.

What's with all of the physics time-travelers from the 1960s? Bell's theorem has repeatedly passed experimental muster, and has become a cornerstone of quantum information theory-- a field which has lead to any number of testable (and subsequently tested) predictions.

It depends on what kind of information you're talking about, classical information or quantum information. You most certainly cannot sent classical information faster than the speed of light. As for the logic behind this thought experiment, you may want to check out:
http://en.wikipedia.org/wiki/Bell's_theorem

A completely valid arguement-- until 1964:
http://en.wikipedia.org/wiki/Bell's_theorem

The probabilities can derived in MWI using work done by Everett and DeWitt in the '50s and by Deutsch and Wallace in 2007.

Actually, proof of concept experiments have already been done for both Shor's algorithm as well as Grover's algorithm.