Why is "the set of all sets" a paradox, in layman's terms? I've heard of some other paradoxes involving sets (i.e., "the set of all sets that do not contain themselves") and I understand how paradoxes arise from them.  But this one I do not understand.
Why is "the set of all sets" a paradox?  It seems like it would be fine, to me.  There is nothing paradoxical about a set containing itself.
Is it something that arises from the "rules of sets" that are involved in more rigorous set theory?
 A: The set of all sets is not a paradox.
When set theory was invented, it was assumed that given any predicate, there was a set containing all the things that satisfied the predicate.  This assumption is called naive comprehension. Unfortunately, this allowed paradoxes like the set of all sets not containing themselves.
So people invented restricted axioms of comprehension. These are rules that say that only certain predicates give rise to sets.  There are different kinds of set theory with different comprehension restrictions.
One idea for limiting comprehension is to say that if the class of things satisfies the predicate is too big, the class is not a set.  All the commonly used set theories use this idea. The set of all sets is very large indeed, so it is not a set in these theories.
There are other ways of restricting comprehension that get rid of the paradoxical sets but do allow a universal set.  One such set theory was invented by Quine and called New Foundations.  There is a book by Holmes, Set Theory with a Universal Set.
A: Just by itself the notion of a universal set is not paradoxical.
It becomes paradoxical when you add the assumption that whenever $\varphi(x)$ is a formula, and $A$ is a preexisting set, then $\{x\in A\mid \varphi(x)\}$ is a set as well.
This is known as bounded comprehension, or separation. The full notion of comprehension was shown to be inconsistent by Russell's paradox. But this version is not so strikingly paradoxical. It is part of many of the modern axiomatizations of set theory, which have yet to be shown inconsistent.
We can show that assuming separation holds, the proof of the Russell paradox really translates to the following thing: If $A$ is a set, then there is a subset of $A$ which is not an element of $A$.
In the presence of a universal set this leads to an outright contradiction, because this subset should be an element of the set of all sets, but it cannot be.
But we may choose to restrict the formulas which can be used in this schema of axioms. Namely, we can say "not every formula should define a subset!", and that's okay. Quine defined a set theory called New Foundations, in which we limit these formulas in a way which allows a universal set to exist. Making it consistent to have the set of all sets, if we agree to restrict other parts of our set theory.
The problem is that the restrictions given by Quine are much harder to work with naively and intuitively. So we prefer to keep the full bounded comprehension schema, in which case the set of all set cannot exist for the reasons above.
While we are at it, perhaps it should be mentioned that the Cantor paradox, the fact that the power set of a universal set must be strictly larger, also fails in Quine's New Foundation for the same reasons. The proof of Cantor's theorem that the power set is strictly larger simply does not go through without using "forbidden"  formulas in the process.
Not to mention that the Cantor paradox fails if we do not assume the power set axiom, namely it might be that not all sets have a power set. So if the universal set does not have a power set, there is no problem in terms of cardinality.
But again, we are taught from the start that these properties should hold for sets, and therefore they seem very natural to us. So the notion of a universal set is paradoxical for us, for that very reason. We are educated with a bias against universal sets. If you were taught that not all sets should have a power set, or that not all sub-collections of a set which are defined by a formula are sets themselves, then neither solution would be problematic. And maybe even you'd find it strange to think of a set theory without a universal set!
A: Perhaps the following image will help take from here:

A: Some of the comments in the previous answers make a subtle mistake, and I think it may be worth clarifying some issues. I am assuming the standard sort of set theory in what follows. 
Cantor's diagonal theorem (mentioned in some of the answers) gives us that for any set $X$, $|X|<|\mathcal P(X)|$. Unlike what some comments claim, this really has nothing to do with cardinalities. All it says is that no map $f\!:X\to\mathcal P(X)$ is onto. The usual proof proceeds by noting that $A=\{x\in X:x\notin f(x)\}$ is not in the range of $f$, because if $A=f(a)$, then $a\in A$ if and only if $a\notin f(a)=A$.
The usual argument for Russell's paradox (also mentioned in some of the answers) proceeds by considering $A=\{a:a\notin a\}$. If $V$ is a set, $A$ would be a set as well (by comprehension, if you wish), and  we reach a contradiction by noting that $A\in A$ if and only if $A\notin A$.
I think it is misleading to think (as some of the comments suggest) that the two proofs are (fundamentally) different. They are essentially the same. 
The point is that if there is a set of all sets (let's call it $V$), then $\mathcal P(V)$ is a set as well (by comprehension) and in fact $\mathcal P(V)=V$ because, on the one hand, any subset of $V$ is a set, and therefore a member of $V$, and on the other hand, any member of $V$ is itself a subset of $V$ (since the members of any set are sets themselves), and therefore a member of $\mathcal P(V)$. 
Now, the identity function is a map from $V$ to $\mathcal P(V)$. Let's call it $f$. The set not in the range of $f$ given to us by the standard proof of Cantor's diagonal theorem recalled above is $A=\{x\in V:x\notin f(x)\}$, which in this case reduces to $\{x:x\notin x\}$, which in turn is precisely the set given by the standard proof of Russell's paradox.
[What to make of this result from a foundational point of view is another matter. In $\mathsf{ZF}$ the conclusion is just that there is no set of all sets, although it is perhaps more accurate to say that the result is used to justify dismissing unrestricted comprehension and adopting instead the version of bounded comprehension used in $\mathsf{ZF}$. In $\mathsf{NF}$ the solution is instead to limit unbounded comprehension by only allowing stratified instances. Other foundational solutions may and have been adopted as well.]   
A: The existence of universal set is incompatible with the Zermelo–Fraenkel axioms of set theory. However, there are alternative set theories which admit a universal set. One such theory is Quine's New Foundations.
A: This turns out to be the same as @donroby's  answer. The scheme is inspired by the proof of Cantor's theorem, the use of which is implicit in the accepted answer.
As the following example shows, if all is construed as commonsense does, the set of all sets contains a member that simultaneously is and is not a member of itself.
Let $T = \{ \alpha \ |\ \alpha $ is a set and $ \alpha \notin \alpha \}$,
$T \in T \Rightarrow T \notin T$   --- (1)
$T \notin T \Rightarrow T \in T$    --- (2)
(1).(2) $\Rightarrow$ Paradox.
Note: This answer dispenses with such higher notions as  "power set," "cardinality" and "less than" whose properties cannot be ascertained before the properties of set are ascertained.
Further analysis leads to Type Theory which uses meaning as a guarding criterion. In Type Theory, all sets, as commonsense understands it, is meaningless; propositions like $T\in T$ and $T \notin T$ are also meaningless.
A: The "set of all sets" is not so much a paradox in itself as something  that inevitably leads to a contradiction, namely the well-known (and referenced in the question) Russell's paradox.
Given any set and a predicate applying to sets, the set of all things satisfying the predicate should be a subset of the original set.  If the "set of all sets" were to exist, because self-containment and non-self-containment are valid predicates, the set of all sets not containing themselves would have to exist as a set in order for our set theory to be consistent.  But this "set of all sets" cannot exist in a consistent set theory because of the Russel paradox.
So the non-existence of the "set of all sets" is a consequence of the fact that presuming it's existence would lead to the contradiction described by Russel's paradox.
This is in fact the origin of Russel's paradox. 
In his work "The Basic Laws of Arithmetic", Gottlob Frege had taken as a postulate the existence of this "set of all sets".  In a letter to Frege, Bertrand Russell essentially blew away the basis of Frege's entire work by describing the paradox and proving that this postulate could not be a part of a consistent set theory.
A: An informal explanation is Russel's Paradox. The wiki page is informative, here's the relevant quote:

Let us call a set "abnormal" if it is
a member of itself, and "normal"
otherwise. For example, take the set
of all squares. That set is not itself
a square, and therefore is not a
member of the set of all squares. So
it is "normal". On the other hand, if
we take the complementary set that
contains all non-squares, that set is
itself not a square and so should be
one of its own members. It is
"abnormal".
Now we consider the set of
all normal sets, R. Attempting to
determine whether R is normal or
abnormal is impossible: If R were a
normal set, it would be contained in
the set of normal sets (itself), and
therefore be abnormal; and if it were
abnormal, it would not be contained in
the set of normal sets (itself), and
therefore be normal. This leads to the
conclusion that R is both normal and
abnormal: Russell's paradox.

A: How about a set that contains everything with the exception of itself?
A: 
"Why is "the set of all sets" a
  paradox? It seems like it would be
  fine, to me."

The lesson of this and other set theory paradoxes is that when you define a set in a proof, you are obliged to demonstrate that the set exists and is well-defined. To me, a paradox of Russell's Paradox is that he fell into this trap since he pretty much wore himself out trying to generate a rigorous foundation for Mathematics.
A: Russel's paradox arises if you consider the set $U=\left\{x:x\not\in x\right\}$. Ask yourself if $U\in U$. If you suppose so, then by the definition of unrestricted set comprehension $U\not\in U$. You have a contradiction, so it must be the opposite of what you supposed, that is, $U\not\in U$. But this is the same as saying $U$ belongs to the complement of itself, that is, $U\in U$. You now have another contradiction, but this is far worse, since you have no hypotheses. The whole theory is logically inconsistent.
In set theory there are two ways for getting rid of the Russel's paradox: either you disallow the set of all sets and other similar sets (see for example the Zermelo-Fraenkel set theory), or you allow them, but you also restrict the way they are used (see for example the Morse-Kelley set theory).
In the first case, set comprehension says if you have a set $A$ you can have $\left\{x\in A:\phi\left(x\right)\right\}$ (notice: writing $\left\{x:\phi\left(x\right)\right\}$ is just wrong in this case, because you have to have an initial set). If you now define $U=\left\{x\in A:x\not\in x\right\}$ and you repeat the same passages as before, it only follows that $U\not\in A$. There's no contradiction and the theory is consistent.
In the second case, you consider classes, not just sets. Sets are classes that belong to some other class, while proper classes are classes that belong to no class. Set comprehension, in this case, says you can have $\left\{x:\phi\left(x\right)\right\}$, but all its members are sets by definition. If try to reproduce Russel's paradox, you get that $U\not\in U$. If you then suppose that $U$ is a set, then you have a contradiction, so $U$ must be a proper class. This is all you get. No contradictions. The theory is consistent.
A: Let $|S|$ be the cardinality of $S$. We know that $|S| < |2^S|$, which can be proven with generalized Cantor's diagonal argument.

Theorem

The set of all sets does not exist.

Proof

Let $S$ be the set of all sets, then $|S| < |2^S|$. But $2^S$ is a subset of $S$. Therefore $|2^S| \leq |S|$. A contradiction. Therefore the set of all sets does not exist.

A: I think this paradoxon is not so complicated and can be explained simply.
If you put all existing sets S(1) to S(k) together in a set S(all), you create a new set S(k+1)={S(1),...,S(k)} and this set has to be in the set of all sets as well (because it should contain all sets). Thus, you put the new set S(k+1) in the set of all sets S(all). But this in turn creates a new set S(k+2)={S(1),...,S(k+1)} wich has to be inserted in the set of all sets as well. Putting S(k+2) in S(all), however, creates a new set and so on and so on.
In conclusion, everytime you put the new set into the set of all sets you create a new set. As a consequence, you can never build a set S(all) that contains all sets without creating a set which is not contained in S(all).
