Why isn't an infinite, flat, nonexpanding universe filled with a uniform matter distribution a solution to Einstein's equation? In Newtonian gravity, an infinite volume filled with a uniform distribution of mass would be in perfect equilibrium. At every point, the gravitational forces contributed by masses in one direction would be exactly counterbalanced by those in the opposite direction.
But when Einstein tried to apply General Relativity to possible cosmologies, he found it necessary to include the cosmological constant in order to get a static universe.
In qualitative terms, it seems to me that the gravitational stresses that the masses would impose on the spacetime should all cancel out, and likewise, that the resulting flat spacetime should have no effect on the motion of the masses. 
However, the math of the situation is beyond my current skills, so I'm asking how it produces the nonequilibrium condition?
(I realize that such an equilibrium solution might not be stable, and that there are many other very good reasons to believe in an expanding universe, so I'm not trying to promote any alternative theories. I'm just curious about this particular point. )
 A: This is a rather subtle question, which confused even Newton. It is very tempting to think that an initially static Newtonian universe with perfectly uniform mass density will not collapse, because the gravitational force cancels everywhere by symmetry. This is wrong.
Here's an analogous question: suppose a function $f$ obeys
$$f''(x) = 1$$
and we want to solve for $f(x)$. Since every point on the real line is the same as every other point, we might think that by symmetry,
$$f(x) = \text{constant}.$$
But this is completely wrong, because the second derivative of a constant is zero. And stepping back, the whole question doesn't make any sense, because there isn't enough information. To solve a general differential equation, you need boundary conditions.
One possible boundary condition is that the solution looks approximately even at infinity. That's enough to specify the solution everywhere, as
$$f(x) = \frac{x^2}{2} + \text{constant}.$$
But now the translational symmetry has been broken: not every point is equivalent anymore, because we have a minimum at $x = 0$. This is inevitable. You can't solve the differential equation without boundary conditions, and any choice of boundary conditions breaks the symmetry.
Similarly in Newton's infinite universe we have
$$\nabla^2 \phi = \rho$$
where $\rho$ is the constant mass density and $\phi$ is the gravitational potential, corresponding to $f$ in the previous example. Just as in that example, we "obviously" have by symmetry
$$\phi(x) = \text{constant}$$
which indicates that the force vanishes everywhere. But this is wrong. Without boundary conditions, the subsequent evolution is not defined; it is like asking to solve for $x$ given only that $x$ is even. With any set of boundary conditions, you will have a point towards which everything collapses. So the answer to your question is that both the Newtonian and relativistic universes immediately start to collapse; the symmetry argument does not work in either one, so there is nothing strange to explain.

The reason this point isn't mentioned in most courses is that we often assume the gravitational potential goes to zero at infinity (in Newtonian gravity) or that the metric is asymptotically flat (in relativity). But this boundary condition doesn't work when the mass distribution extends to infinity as well, which leads to the pitfall here. The same point can lead to surprises in electrostatics.
We reasoned above in terms of potentials. A slightly different, but physically equivalent way of coming to the same conclusion is to directly use fields, by integrating the gravitational field due to each mass. In this case, the problem is that the field at any point isn't well-defined because the integrals don't converge. The only way to ensure convergence is to introduce a "regulator", which makes distant masses contribute less by fiat. But any such regulator, by effectively replacing the infinite distribution with a finite one, introduces a center towards which everything collapses; just like the boundary conditions, any regulator breaks the symmetry. So, again, collapse immediately begins.
In the end, both the Newtonian and relativistic universes immediately begin to collapse, and in both cases this can be prevented by adding a cosmological constant.  In the Newtonian case, this is simply the trivial statement that $\nabla^2 \phi = \rho - \Lambda$ has constant solutions for $\phi$ when $\rho = \Lambda$. However, in both cases the solution is unstable: collapse will begin upon the introduction of any perturbations.
A: 
In qualitative terms, it seems to me that the gravitational stresses that the masses would impose on the spacetime should all cancel out, and likewise, that the resulting flat spacetime should have no effect on the motion of the masses.

I think there is a subtle misunderstanding here.
In general relativity, a universe uniformly filled with mass (or really with energy) will see all the forces acting on a massive object cancel, as in the Newtonian case. This is due to the symmetries of a uniform universe.
However, this does not mean that the universe is flat.
In Newtonian mechanics, forces cancelling each other implies a motion following a straight line. Then intuitively it seems like an object could definitely not follow a straight line in a curved space time. But here is the catch: in the context of general relativity, the concept of straight line does not make much sense.
To understand why, we must ask ourselves what is a straight line. In Newtonian mechanics it is easy: it is the path followed by an inertial object, i.e. an object on which we can define a reference frame such that this object in this frame seems to be static and affected by no forces.
The principle of equivalence of general relativity, however, tells us that such a frame can in fact be defined for any free-falling object (object only affected by gravitational forces). The trajectories of such objects are called geodesics and that is the best we can do to extend the Newtonian concept of straight line. In other words, in general relativity "straightness" is an effect of reference frame.
Then, not very surprisingly, in a universe where we consider only gravitation, all objects follow geodesics and thus are moving following "generalized straight lines".
What all of that indicates is that considerations on objects' motion do not give us (to my knowledge) any information about the structure of space and time. Unfortunately this answer does not explain the necessity of an expanding universe, just point out the Newtonian argument is limited. The reason is that as far as I know there is no simple intuitive explanation of the reason behind the expansion of the universe.
A: In Principia Newton introduces the Iron Sphere theorem, which says that you can ignore the gravitational effects of a spherically symmetrical distribution of matter outside of a given sphere.  This implies that a uniform distribution of matter should collapse to a point.  But there's a problem here: Newton thought in terms of absolute space, and so there's no reason it should collapse to one point rather than another.
The idea of gravity 'cancelling out' in a uniform distribution was discussed in correspondence with Richard Bentley, who was very much part of the religious establishment.  My impression is that Newton was happy to seem agreeable here. Principia was OK, but he didn't want the Church investigating his other works too closely.  The 'cancelling out' argument pushes the problem off to infinity (so it gives God something to do)
It wasn't particularly satisfactory though, and in 1759 Roger Boscovich proposed a repulsive force to keep matter in balance, essentially an early version of the cosmological constant (this was later developed by William Herschel)
For Einstein though it wasn't possible to push the problem off to infinity, since relativity has to be local.  Hence the cosmological constant. (But E.A Milne did use a version of the 'cancelling out' argument for his universe which was expanding but disregarded gravity on large scales)
A: The equation governing the curvature of spacetime in general relativity is
$$
R_{\mu\nu} - \frac12Rg_{\mu\nu} = \frac{8\pi G}{c^4}T_{\mu\nu}
$$
Or, really, it's $16$ equations in one: $\mu$ and $\nu$ can both take values from $0$ to $3$, representing the four components of any given coordinate system, and for each such choice you get a new equation (with the small caveat that it is symmetric in $\mu$ and $\nu$, so really, it's only $10$ distinct equations).
The symbols $R_{\mu\nu}$, $R$, $g_{\mu\nu}$ and $T_{\mu\nu}$ are so-called tensors, which for now you can think of as real-valued functions on spacetime. (The actual values you get will be dependent on your choice of coordinate system, but if you fix one coordinate system for the region you're interested in they do become just functions. $R$ is a single function while the remaining three, again, are collections of $16$ functions: one for each $\mu, \nu$ pair.)
The left-hand side represents the curvature of spacetime. In flat spacetime we have $R_{\mu\nu} = 0$ for any $\mu, \nu$, and we also get $R = 0$, so the left-hand side will be $0$.
The right-hand side is one big constant multiplied by $T_{\mu\nu}$, which represents the energy at each point in space. In a "sensible" coordinate system (where the $0$-component represents time, and the three remaining coordinates represent space), $T_{00}$ will represent the energy density (including mass density; the other components of $T_{\mu\nu}$ represent things like pressure and momentum density). If there is uniform non-zero mass everywhere, then $T_{00}$ will be non-zero. That means that $R_{00} -\frac12Rg_{00}$ will also be non-zero, which means that we do not have flat spacetime as either $R_{00}$ or $R$ must be non-zero.
In order to regain flat spacetime in this case, and allow both $R_{\mu\nu}$ and $R$ to be zero, it is necessary to add a third term to the left-hand side: the cosmological constant $\Lambda$, giving us
$$
R_{\mu\nu} - \frac12Rg_{\mu\nu} + \Lambda g_{\mu\nu} = \frac{8\pi G}{c^4}T_{\mu\nu}
$$
A: Nice question!
Here's a possible statement of the logic in the newtonian case. (1) In newtonian mechanics, we assume that inertial reference frames exist (this is one popular modern way of restating Newton's first law), we assume that such frames are global, and we assume that we can always find such a frame by observing a test particle that is not acted on by any force. (2) In the newtonian homogeneous cosmology, we could assume that the force on a chosen test particle P can be found by some limiting process, and that the result is unique. (This is basically a bogus assumption, but I don't think that ends up being the issue here.) (3) Given that the result is unique, it must be zero by symmetry. (4) By assumptions 1 and 2, P defines an inertial frame, and by assumption 1, that frame can be extended to cover the entire universe. Therefore all other particles in the universe must have zero acceleration relative to P.
In general relativity, assumption 1 fails. Test particles P and Q can both be inertial (i.e., no nongravitational forces act on them), but it can be false that they are not accelerated relative to one another. For example, we can make an FRW cosmology in which, at some initial time, $\dot{a}=0$, but then it will have $\ddot{a}\ne0$ (in order to satisfy the Einstein field equations for a uniform dust). (In this situation, the Einstein field equations can be reduced to the Friedmann equations, one of which is $\ddot{a}/a=-(4\pi/3)\rho$.)
This shows that the newtonian argument (or at least one version of it) fails. It does not prove that there is no other semi-newtonian plausibility argument that explains why an initially static universe collapses. However, I'm not sure what criteria we would be able to agree on as to what constitutes an acceptable semi-newtonian plausibility argument. Some people have developed these semi-newtonian descriptions of cosmology at great length, but to me they appear to lack any logical foundations that would allow one to tell a correct argument from an incorrect one.
A: Your question is rather deep and the other answers get to the heart of "what's really going on", but I wanted to just step back and clarify something simple which I don't think anyone else has explicitly pointed out yet:

In Newtonian gravity, an infinite volume filled with a uniform distribution of mass would be in perfect equilibrium. At every point, the gravitational forces contributed by masses in one direction would be exactly counterbalanced by those in the opposite direction.

As other people have pointed out, this is incorrect, for rather subtle conceptual reasons involving the nature of the infinite-space limit. But there's an extremely simple way to see mathematically why an uniform mass density $\rho$ cannot produce an identically zero gravitational field ${\bf g} \equiv {\bf 0}$: Gauss's law for gravity says that ${\bf \nabla} \cdot {\bf g} = -4\pi G \rho$, or equivalently $\iint_{\partial V} {\bf g} \cdot d{\bf A} = -4 \pi G\, M_\text{enclosed}$. It's very clear that ${\bf g} \equiv {\bf 0},\ \rho =$ (nonzero constant) does not satisfy these equations.
A: One more perspective: the question is essentially why the solution to the relevant equation of motion doesn't have the same symmetry as the EOM does. This isn't a unique feature of gravity!
EOM symmetries are closure rules for the solution set, not properties of individual solutions; for example, the translational invariance of $f^{\prime\prime}=c$ means that if $f(x)$ is a solution so is $f(x-a)$, not that $f(x)\equiv f(x-a)$. Once boundary conditions specify one solution, neither the conditions nor the solution keeps the EOM symmetry; the former explains the latter.
This is called spontaneous symmetry breaking. Sure, that term usually comes up when a complex scalar's Lagrangian is invariant under phase shifts, but that's a historical accident from when we were thinking about the Higgs field. The principle is general. Here's a much simpler application of it to gravity than in the OP: if you hold up a pen with a fingertip, while one end balances on a table, when you let go it falls in a specific direction. The symmetry has been broken.
