Paradox with Gauss' law when space is uniformly charged everywhere Consider that space is uniformly charged everywhere, i.e., filled with a uniform charge distribution, $\rho$, everywhere.
By symmetry, the electric field is zero everywhere. (If I take any point in space and try to find the electric field at this point, there will always be equal contributions from volume charge elements around that point that will vectorially add up to zero).
Consequently, from Gauss' law in the differential form  $$\nabla\cdot E = \frac{\rho}{\epsilon_0}$$
if $E$ is zero, the divergence is zero hence the charge density is zero.
What is going on here? is a nonzero uniform charge distribution that exists everywhere has no effect and is equivalent to no charge at all?
 A: If you followed the arguments carefully and checked what is demonstrably right and what is not, you would agree that what the argument actually does is to prove that a uniform electric charge density cannot have a uniform electric field. Your original task was to solve Maxwell's equations (well, Gauss's law), so if you find out that the equations aren't satisfied, it just means that you haven't solved the problem you wanted to solve, or that the candidate solution is wrong. You can't suddenly say – as your question suggests – that it doesn't matter that the equations aren't solved and you want to change them or something else. This would be changing the rules of the game – and changing the laws of physics.
Instead, you will be able to find solutions $\vec E(x,y,z)$ which obey ${\rm div}\,\vec E = \rho/\epsilon_0$. However, it is not true that this $\vec E(x,y,z)$ may be translationally symmetric. Instead, you must pick an origin where $\vec E = 0$, let's say at $(x,y,z)=(0,0,0)$, and write
$$ \vec E = \frac{\rho}{\epsilon_0} (x/3, y/3, z/3) $$
Feel free to check that the divergence is what you wanted it to be. You may also write this $\vec E$ from a potential, $\vec E = -\nabla \phi$,  $\phi = \rho/(2\epsilon_0) (x^2+y^2+z^3)/3 $. I could actually divide the terms asymmetrically to the coordinates $x,y,z$.
The same "paradox" arises in the case of the gravitational acceleration and mass density. In the non-relativistic case, this surprising non-uniformity of $\vec E$, while not paradox, strongly suggests that at the longest scale, the charge density should be zero. And it's indeed the case of the electric charge density. For the mass density, it's not the case although the Newtonian argument would still lead us to conclude that it should be true. However, the mass can't be negative and the energy density is positive. This would force a violation of the translational symmetry in a uniform Newtonian Universe. However, the Einsteinian (well, FRW) universe obeying the laws of general relativity has no problem with an overall positive mass density: the Universe just gets curved accordingly. Our Universe is an example.
A: 
What is going on here?

Others have noted this apparent inconsistency:  Gauss’ Law PROVED WRONG!
I suspect that what's going on here is that the (lack of appropriate) boundary conditions do not guarantee a unique E field.
See Wiki's Uniqueness theorem for Poisson's equation
A: Adding a slightly different rewording, since this is a subtle issue that has come up in one form or another again and again and again and again in one form or another. The end result is the same whether we are considering electric charge (which can have both positive and negative values) or mass (which of course can only be nonnegative).
At the heart of the issue is trying to describe properties of a system that is not well-defined. Forget about equilibrium; an infinite homogeneous distribution runs into existence issues long before that comes up.
Any physical distribution of charge (of the electric or mass type) should be attainable in the limit of a (countable) sequence of finite distributions, for which the physics is on solid ground. Add a little bit here, then a little bit there. However, there are multiple ways to add, e.g., shells of material, such that the limit of the process is "an infinite, uniform distribution," and they do not agree in all respects.
Consider a point $\vec{r}$ in $\mathbb{R}^3$, where the origin is chosen to be elsewhere. Consider adding spherical shells of charge centered at the origin, starting with the smallest ones. The first few will induce a net acceleration of any charge at $\vec{r}$, but after a point the shells will encompass $\vec{r}$ and so will make no contribution to the acceleration. Summing up, the total effect is nonzero. However, a different choice of origin, which should have been arbitrary, leads to a different result. The quantities you want to associate with the infinite distribution (electric field, gravitational potential, whatever) depend on how you construct it, and there is no clear "natural" way to do it.
Your infinite distribution, taken in the positivist sense to include all the effects it can have on observables, simply doesn't exist (mathematically, not just physically), and so we cannot speculate on what those effects on observable might be.
A: Few Comments:


*

*If all "points" in space are equally charged, then it will define new vacuum. This is a global reference. It is like a Dirac sea. So, maybe the vacuum Dielectric constant was different.  

*Choosing a point, to be the "zero" point, doesn't break the translation invariance of the space, unless mathematically speaking, the measure of that zero point in the space is non-zero. That is, the measure of a point out of R is zero. However, the measure of a point, out of discrete space is non-zero (because the set is countable). 
In case that the zero point posses non-zero measure, the space becomes curved around the elected "zero" point (as mentioned above, everything is canceled, but not the zero point contribution). 
E. Atzmon 
A: Also in simple terms. In a universe that is infinite with a uniform distribution of dark matter you are always in the center of that distribution. Gravity in a spherical shell, if you work it out, always goes to zero inside a spherical shell. This is why gravity in the earth doesn't go to infinity. Approaching the earth gravity increases with distance by 1/r^2. However, when we reach the earth and pass through the outer spherical shell of matter, the gravity from that shell now cancels. The volume of that matter decreases as a function of r^3. The result after you do the math is a linear decrease in gravity till it goes to zero in the center of the earth. An infinite universe of evenly distributed matter with no defined center contributes zero gravity everywhere because you are always in the center of a sphere. This might make us question if such an infinity can truly exist.  At least logic seems to assimilate the idea of infinity.
The static electric field can be viewed similarly in this case to that of the gravitational field.  
A: I think we can agree that if all space carries a fixed and uniform charge density (in our frame) then the E field is zero everywhere. Obviously then, the flux calculation for any closed surface will yield zero as well despite the presence of "charge" within the bounded region.
Thinking "physically" and a bit less mathematically, it seems to me this so-called paradox comes down to our interpretation of div(E) ~ rho. Perhaps we should always think of this equation as:
div (E) ~ rho - rho(0), where rho(0) is the charge density of the "vacuum". 
From the standpoint of electrostatics, if we add a uniform (in my frame) rho(0) charge density everywhere -- there will be no change in the static E-field due to "over densities" of charge. For example, the E-field associated with a lonely electron will look the same if I add a uniform rho(0) background charge density everywhere around it (well, and AT it too). 
If we recognize that a rho(0) charge density does not change the physical field E -- it's easy to see how div (E) ~ rho - rho(0) gets us back to where we want to be with flux calculations and charges. This is a "gauge"-ie sort of argument and it makes practical, physical sense to me.
Now the interesting thing is whether or not a background diffuse uniform charge density (rho(0)) as seen in MY frame would look the same to a boosted frame. I don't have the chops at the moment to work this out, but my instincts tell me that in relative, boosted frames what looks like a uniform rho(0) may be transformed into something that may not be uniform -- -- even though it's a scalar (the volumes and transverse differences probably come into play). But this needs to be checked (a nice undergrad EM exercise). In addition, in boosted or rotating frames I suspect rho(0) -- as seen in my "rest frame" -- looks like currents and things are a mess (although nicely prescribed by Maxwell's Eqns). Again, I have not done the analysis -- but there may be some interesting EM/relativistic effects related to a background charge density that appears uniform in at least one frame (for which one seems to run into a paradox about Gauss's Theorem).
Anyways, I think the resolution of the paradox rests on a recognition that physical fields -- like E -- arise from DIFFERENCES in source densities from a uniform ground for which the associated physical fields are zero.
Sound right?
A: Just a quick point about your symmetry argument. The exact cancellation of all electric field contributions at a point $P$ goes wrong because there is no contribution to cancel the contribution from the charge element at $P$ itself. As other posters stated, you must start with Gauss' Law as written and integrate your given charge density. You won't get a uniformly zero electric field.
A: I want to add a new perspective to user10851's comment. As it is already discussed, the solution we want, where we have constant electric density everywhere, is non-zero. Besides, it increases as we get further away from the origin.
It can be argued that the problem is that we can choose origin arbitrarily such that we find exactly the same solution for any point as origin, which seems contradictory because if one asks "what is the electric field at a point $P$?", then we cannot give an answer independently from the origin, i.e. the electric field is origin-dependent (observer dependent).
The perspective I propose is this:
THIS SOLUTION IS EXACTLY IDENTICAL TO THE EXPANSION OF OUR UNIVERSE
Our universe is homogeneous but at the same time it is expanding. As it is in the user10851's solution, the expansion is stronger as we get further from the origin of our reference frame. As it is in the solution, the expansion depends on the reference frame we choose.
Thus, the problem in your argument was that the assumption that homogeneity of charge density implies electric field is zero everywhere. As we have seen, it does not.
IMPORTANT NOTE: The expansion of universe is only an example to show that homogeneous does not imply stability. I, of course, do not propose the expansion of the universe is related to charge or electric field
