Why must entangled particles communicate their spin instantaneously? I'm a complete newbie to Quantum Theory, but I want to know more, so I've been watching few YouTube videos (an example below). 
https://www.youtube.com/watch?v=ZuvK-od647c
All videos I've watched explain, that when an entangled particle has its spin measured, it will instantaneously communicate its measurement with its entangled partner, so that when it too is measured in the same direction, it will have the opposite spin. 
Often these videos explain why these particles must be communicating with each other, rather than containing "hidden information" (Bell's theorem), but do not delve into why it must be instant. 
 A: A very good question because "instantaneous" is not really meaningful within the framework of special relativity. "Instantaneous" would imply the observation of the two particle states at the same time, but that will depend on our reference frame. See https://en.wikipedia.org/wiki/Spacetime#Relativity_of_simultaneity. 
What they really mean in these videos, and what experiments reveal, is that the states of the two particles are correlated even when the two measurements take place outside of each other's light cones. In other words we see correlation even when there is a spacelike separation between the two measurements. Current theories do not allow information travel between the two spacelike separated measurements. 
(BTW with spacelike separation we can always find a reference frame whose observer will see the two measurements really happen at the same time.) 
You might be interested in this article about a specific 2013 experiment. The events are laid out in this diagram:

There is no (known) way that the result of measurement A could have influenced the outcome of measurement B or vice versa. But "communicating instantaneously" is still grossly misleading. 
A: Here is an experimentalist's answer:
Quantum mechanics is the underlying framework of nature from which the classical framework emerges. It is a mathematical model which depends on postulates, like extra axioms, to pick from all the possible solutions of the quantum mechanical wave equations , those that fit the data. Up to now there has been no falsification in these calculations. i.e. they describe existing data and predict new  situations successfully.
The QM model predicts probability densities, i.e. the mathematical solutions, the wavefunctions which are defined by the boundary conditions of the problem, when complex conjugate squared, give the probability density distribution for an interaction or a decay or....  Experimentally probability densities are built up event per event, and then the distributions are checked against the predictions of the theory.
The wavefunction is not a measurable quantity, it is only the accumulation of many events that can validate the wavefunction.
Wavefunctions cover all of the available phase space in space and time, and the conservation laws hold for individual events. For example the wavefunction for scattering two electrons contains all the probabilities for the scattering of an electron on another electron and  their spins summing to zero,  all the spin information is contained in the wavefunction. When a single event is measured, i.e. one electron is measured to have spin 1/2 , conservation laws will tell us that the other has spin -1/2, immediately. There is no transfer of information.
Things get more complicated for solutions of relativistic differential  equations,  because there may be solutions/wavefunctions which  may have a mathematical description outside the  light cone. Since we know that faster than light communication is experimentally excluded, it means that this particular solution cannot be used to describe a physically meaningful situation. See my answer to a relevant  question here.
Entanglement is a shorthand way of saying there exists a complete quantum mechanical solution for theses boundary conditions and this system. If the solution is valid, it contains by construction all the information, nothing is communicated, it is just described/modeled.
A: Any talk of 'instantaneous communication' is, at best, a lie-to-children: an oversimplification that does not actually work and which misrepresent important aspects of the topic, but which is vaguely suitable as a first approach to the subject. We do not fully understand entanglement as well as we would like, but very few serious physicists working on the topic believe that there is such a communication.
However, the Veritasium video you linked to is very careful to avoid that trap, and Derek Muller never states that the particles communicate: if you actually listen to what he says,

when one particle is measured and its spin is determined, you immediately know what the same measurement of the other particle will be

he makes it clear that any instantaneousness is on the part of the observer, and not a physical communication between the particles; the same is true with the later quote

it's as if the choice of the measurement has influenced the result of the second, faster than the speed of light, which is indeed how some theorists interpret the result.

It is extremely hard to reconcile any notion of instantaneous communication with special relativity, because in SR simultaneity is a relative concept: in one frame of reference the two measurements might look instantaneous, but if you examine the experiment in a different inertial frame, then the measurement on particle B happens before the one on A. Given that, how can A communicate its experiences to B and get the information there before it's measured?
So, why isn't this a problem? Well, as mentioned in the video, entanglement cannot be used to communicate, and no physical phenomenon is available to us that breaks with special relativity. Any impression of simultaneity or instantaneousness is entirely an artifact of how we observe things and how we interpret them.
Now, this might sound like a pretty waffly and noncommittal answer, and it might also sound like we don't really understand entanglement as well as we would like. That last bit is completely accurate, and anyone that tells you that they understand it is fooling themself. Quantum mechanics suggests that, if there is any underlying reality that we then measure, that reality is nonlocal in some sense, but so far the nature of that nonlocality has proved to be extremely elusive. It is very tempting to do as kpv has done in the accepted answer and fill that gap with speculation, but frankly, I don't think that that's particularly helpful. There's stuff that we don't understand and it's OK to leave it at that.
A: Do they explicitly say "communicate", or are you paraphrasing? Because communicate's wrong. At least, when the spin measurement events are separated by a space-like interval (which are the situations where entanglement's mysterious), communication's >>impossible<<. So in those situations, entangled particles simply aren't communicating.
Let me give you a non-mysterious classical example. Suppose you hide two balls in two identical-looking boxes, a red ball in one and a blue ball in the other. Now, I hasten to immediately say that's >>not<< like entanglement -- the ball colors are predetermined (I'll give you a non-predetermined classical-like example below). Anyway, suppose you now separate your two boxes by several miles (or light-years if you like). If somebody opens one box and sees a red ball, then we know somebody opening the other box will see blue. Right? But no "communication" is necessary. Right?
Well, that's exactly what happens with entangled particles. No mystery, except for the following, which is where that promised non-predetermined example comes in, as follows. Instead of two balls, suppose each box contains a coin that you flipped in the air, and the coins are still spinning. They'll eventually land heads-or-tails, but they don't land until their respective box is opened. The mystery is that if they're "entangled", then if one lands heads, the other lands tails, and vice versa. So you'd infer that there must somehow be some "communicating" going on.
However, by analogy with our spin-entangled particles, we know for sure there's no communication. And that's the mystery -- we can't intuitively reconcile our classical thinking, as illustrated by our balls/coins examples, with that nonclassical reality. To summarize the thinking illustrated by those classical examples, recall that the balls don't communicate but there's no mystery about the correlation between their outcomes. The coins also don't communicate, but now any observed correlation is unexpected/mysterious. Ditto the spin-entangled particles. But "communicating" isn't the answer (nobody yet has an intuitively satisfying answer).
Edit since the comment below got several up-votes, let me expand that remark a bit as follows...
The observed correlation between measurements of entangled particles, whenever the measurement events are separated by a space-like interval, cannot be explained by cause-and-effect "communication". Call the two measurement events $m_1$ and $m_2$. Then one observer may see $m_1$ occurring before $m_2$ while a second observer (in a different inertial frame) may see $m_2$ occurring before $m_1$. So there's no unambiguous way to say which came first, the   $m_1=\mbox{chicken}$   or the   $m_2=\mbox{egg}$   (sorry, I couldn't resist:). So you cannot say one "caused" the other, simply because you can't even say one occurred before the other.
The only thing you can unambiguously say is that the single preparation event that prepared both particles in a single entangled state occurred before both subsequent measurements (it's in both their past light cones). And it's that preparation event which somehow "caused" the subsequent measurement correlation. That is, it didn't cause each individual measurement outcome, per se, because they're ultimately random, but it did somehow cause the correlation between them.
And while you're probably thinking, "Huh?...how do you cause a correlation without causing the correlated events?", that's likely a problem with our intuition developed over a lifetime observing classical phenomena.
A: There are three kinds of possibilities that can explain the COMBINATION of two types of below observations relating to entanglement.


*

*Correlation of two particles of any single entangled pair. Perfect anti correlation (opposite spins when measured in same direction) is a specific case of this, which is most commonly sighted

*Statistical correlation between measurement outcomes of numerous pairs when measured at any angles. 1.) can also be considered a special case of 2.)
In order to explain above combination of observations, three kinds of possibilities are there. These are just possibilities, no one knows how actually the correlations form.
1) There is an active link between the two particles of entangled pair that is able to signal at FTL, thus measurement of one particle influences the state of other and then it is easy to expect the observed statistical correlation. This possibility is the one you are talking about and it is also most commonly assumed by most public when they try to explain/understand the correlations.
By signal, here I mean the means by which the entanglement is supposedly collapsed on measurement of first particle. This signal can not be used/detected by any observer for any/information/communication purpose. It just a speculation on how the entanglement may be collapsing. see no-communication theorem on wiki.
2) Reality/Locality is not as we understand it. Meaning, two particles, being spatially far off can still be considered at same location in quantum sense. This allows measurement of one particle to influence that of the other without violating light speed and then it is easy to expect the observed statistical correlation. This appears to be the line taken by most main stream scientists.
3) There is a yet to be discovered classical mechanism that forms the statistical correlations over duration of the experiment. Local Hidden Variables alone is not sufficient to support such mechanism and that has been proven by Bell's inequality and supported by experimental outcomes.
In order for such a mechanism to be at work, it has to involve "Local Hidden Variables" PLUS some kind of global memory/accumulation/balancing/synchronization. Global means that the the natural environment in the vicinity of the experiment accumulates information about creation and measurement outcomes of previous pairs and steers the creation and measurement outcomes of subsequent pairs in such a way that it balances out per quantum mechanics, over large number of pairs.
I have not seen enough literature which would convince that this possibility (3) has completely, critically and honestly been ruled out. Most literature mentions Bell's inequality that only disproves local hidden variables.
Some people also speculate many worlds, which in my opinion is even more weird.
Some people also try to explain it in terms of random probability just like toss of coin eventually turns out ~50/50 percent heads and tails. This explanation becomes weak when you try to explain both kinds of observations listed in the beginning of this answer. You can not explain perfect anticorrelation as random probability. For some states, perfect anticorrelation is guaranteed. There are no guarantees in randomness.
