A binomial distribution is the distribution of the number of successes of n independent, identical Bernoulli trials. What happens when the trials are dependent and the Bernoulli trials are not identical by which I mean that the probability of success from trial to trial varies? How identical and close to independent do they have to be before we see something that resembles a binomial distribution?
You are asking, I think, when a Central Limit Theorem holds. The simplest form of the CLT is that the binomial distributions Binomial(n,p), suitably rescaled, converge to a normal distribution as n goes to infinity. (This binomial case is usually not called the CLT, but goes under the name of the de MoivreLaplace theorem.)
Now, a Binomial(n,p) random variable is the sum of n Bernoulli(p) random variables. The usual form of the CLT states that if $S\_n = X\_1 + ... + X\_n$, where the $X\_i$ are independent and identically distributed with mean μ and standard deviation σ, then $(S\_n  \mu n)/(\sigma \sqrt{n})$ converges in distribution to the standard normal as n → ∞.
If the $X\_i$ are in fact dependent, see the link provided by Ori GurelGurevich above.
If the $X\_i$ are independent but not identically distributed, then there are two standard conditions for proving that the rescaled distribution of $S\_n = X\_1 + ... + X\_n$ converges to the standard normal: Lindeberg's condition and Lyapunov's condition. Both are a bit difficult to understand when you first look at them. But the basic idea behind both of them is that if no one of the summands $X\_i$ is too large (in variance) compared to the others, then the normal distribution still appears.
Depending on your setting, it might better to consider the asymptotic when $n\rightarrow \infty$, which gives you a Poisson distribution. There are various conditions, weaker than independence, under which Poisson approximation holds. For example, take a look here.

$\begingroup$ Also at Pemantle's web page (math.upenn.edu/~pemantle/fullyearwebpage.html) are links to two articles by Arratia, Goldstein, and Gordon on which the lecture you linked to is based. $\endgroup$ – Michael Lugo Nov 11 '09 at 22:58
The distribution you describe is called a Poissonbinomial distribution. If you do a search with this name you will find a substantial literature on it.