How is Liouville's theorem compatible with the Second Law? The second law says that entropy can only increase, and entropy is proportional to phase space volume. But Liouville's theorem says that phase space volume is constant.
Taken naively, this seems to imply that the entropy can never change. What's wrong with the reasoning here?
 A: Your logic is actually correct. The discordance between the conservation of phase-space volume according to the Liouville theorem and the Second Law is known as the Ergodic Problem. Heuristic explanations as the one provided by Ross Millikan, or course graining the dynamics for another example, do not hold under closer formal examination, since the math rigor consistently breaks down at some point or other. There is a rich history (read large number of toms) of trying to rigorously eliminate said discordance, but the ergodic problem is theoretically still open. Practically, however, nobody cares much as long as the techniques of non-equilibrium statistical mechanics, quantum (fields included) or classical, produce meaningful results that can be used consistently.
A: Infinitesimal Perturbations
It is true that entropy would not increase in a completely isolated system that had no perturbations.
As a system evolves the phase space often distorts, elongating and forming twists or folds. Generally as this process progresses, the whole accessible space becomes covered, but with gaps so as to maintain the original volume. As time progresses the width of those gaps becomes smaller and smaller. This thinning process can be seen in this lovely gif from wiki commons:

Now if the system was perturbed by an amount less than or equal to half the width of those gaps, then suddenly the entire volume would be filled in. In any real system there are always perturbations from things like black-body radiation, or debatably even fluctuations in vacuum energy. While these perturbations are small, they increase the volume of the phase space proportionally to the surface area, which in turn would increases continuously other than the decrease do to the perturbations closing the gaps. Thus eventually any size perturbation will significantly effect the phase space volume and thus entropy.
A: I think the intended question was about a thermally isolated system, so no heat could be exchanged; work exchange is allowed.

What's wrong with the reasoning here?

In short, the statistical entropy that is defined for any equilibrium state and can increase in thermally isolated system is not the same thing as the information entropy - a functional of the probability density (or phase space volume where the probability density is the same everywhere) that has to remain constant due to the Liouville theorem. These two entropies are related, but they are not the same concept nor do they always have the same value.
1)

The second law says that entropy can only increase

More accurately, it says that when state is changed from equilibrium state A to equilibrium state B, thermodynamic entropy cannot decrease. Equilibrium state can be specified by stating values of sufficient number of macroscopic variables $X_1,X_2,...$. (For example, equilibrium state of an ideal gas is specified by giving values of volume $V$ and internal energy $U$.) Then thermodynamic entropy function $S(\mathbf X)$ of these state variables can be introduced.
With this, the non-decrease of entropy can now be stated mathematically in this way:
$$
S(\mathbf X_B) \geq S(\mathbf X_A).
$$
2)

entropy is proportional to phase space volume.

More accurately, statistical entropy of an equilibrium state specified by macroscopic variables $X_1,X_2,...$ is proportional to logarithm of volume of certain phase space region. It is believed statistical entropy gives accurate replacement for thermodynamic entropy function (which is the subject of the 2nd law).
The phase space region used above is defined as follows. Any point of phase space represents possible state of the Hamiltonian system (so-called microstate). Not all microstates are compatible with the macroscopic variables $X_1,...$; those that are form the region. Let us denote volume of this region by $\Omega(\mathbf X)$. The statistical entropy of macrostate $\mathbf X$ is defined by
$$
S^{(stat)}(\mathbf X) = k_B \log \Omega(\mathbf X).
$$
Thus statistical entropy is a function of volume $\Omega$, which in turn is a function of the macroscopic variables $\mathbf X$. If the state changes, $\Omega$ may change; and if it does, so does $S^{(stat)}$.
3)

Liouville's theorem says that phase space volume is constant

That is true, but only within the right context. The volume that is sometimes used to formulate the Liouville theorem is a different thing from the volumes $\Omega(\mathbf X_A), \Omega(\mathbf X_B)$ used to define entropy.
The difference is that in the definition of statistical entropy $S^{(stat)}$, the volume $\Omega$ is a function of macroscopic variables $\mathbf X$; it is not a function of time. Consequently, statistical entropy is not a function of time. It does not evolve from lower to higher value continuously in time. It is not necessarily defined for all times between the time $t_1$ where the system is in state A and time $t_2$  where the system is in state B. It is only defined for equilibrium states; in our case, we consider only states A and B.
On the other hand, a popular way to state the Liouville theorem is:
Volume of moving points selected in past remains constant in time.
More accurately, the Liouville theorem implies that if at some time $t_1$ we select points forming a phase space region $R_1$ of definite volume $\Delta\omega_{R_1}$, then at some later time $t_2$, those same points may be elsewhere and form a region $R_2$ of entirely different shape, but its volume $\Delta\omega_{R_2}$ equals $\Delta\omega_{R_1}$. It follows that we can introduce a function of time $\Delta\omega(t)$ that gives volume of the region considered at any time as it moves. It is a constant function:
$$
\Delta\omega(t_1) = \Delta\omega(t) = \Delta\omega(t_2) ~~~\forall t\in\langle t_1;t_2\rangle.
$$
You may ask: couldn't we apply this to volume $\Omega(\mathbf X_A)$, so the observed volume $\Delta \omega$ would actually be equal to the volume of the whole phase space $\Omega(\mathbf X_A)$? Wouldn't it then follow that $\Omega$ cannot change and thus we must have $\Omega(\mathbf X_A) = \Omega(\mathbf X_B)$?
We could, as a special application of the Liouville theorem, do just that. As time goes by, the observed points will be moving and the region they define may change its shape.
$$
\Delta \omega(t_1) = \Omega(\mathbf X_A) = \Delta \omega(t)~~~\forall t\in\langle t_1;t_2\rangle.
$$
So indeed the phase space volume of observed points does not change in time. But isn't this a problem? What if we calculate the statistical entropy as
$$
S^{(stat)}(\mathbf X_B) = k_B \log \Delta \omega(t_2) ?
$$
This has to have the same value as
$$
S^{(stat)}(\mathbf X_A) = k_B \log \Delta \omega(t_1).
$$
But if so, this prevents having higher entropy in the final state B.
The actual problem is that the formula for statistical entropy is not, as some believe
$$
S^{(stat)}(t) = k_B\log \Delta\omega(t)
$$
where $\Delta\omega(t)$ is volume of phase space occupied by observed set of points obtained as a result of Hamiltonian evolution in time. That is a different notion, a special case of information entropy that is a functional of probability distribution, and thus may be a function of time. In this situation, where there is no heat transfer so the Liouville theorem applies, the information entropy remains constant in time, even if statistical entropy does not.
The correct formula for calculating statistical entropy is based solely on the macroscopic thermodynamic variables, not time. We know that by assumption, the system at time $t_2$ is in macroscopic state $\mathbf X_B$. The phase space volume corresponding to this state is $\Omega(\mathbf X_B)$. If it is greater than $\Omega(\mathbf X_A)$, the statistical entropy has increased. It is this phase volume based on macroscopic variables, not the volume of the observed points in the phase space, that is important for statistical entropy. The volume of phase space compatible with state B may be much higher than volume of phase space compatible with Hamiltonian evolution from A at time $t_1$ to B at time $t_2$.
A: Jaynes has a compelling argument whereby he actually "proves" the 2nd law (or an aspect of it, at least), using Liouville's theorem, which goes roughly like this:
Say you have a system which is measured to be in macrostate A, and it reproduceably evolves to macrostate B in a time $\tau$.  We don't know the microscopic details of state A, and it corresponds to a region of phase space $P(A)$.  Similarly, state B corresponds to a region $P(B)$.  Given that A reliably evolves to B, then any microstate compatible with A must evolve to a microstate compatible with B.  Well then, in phase space, start with a phase space volume of all points that are microstates of A.  They apparently all evolve to B by the time $t=\tau$, and the phase space cloud (which has the same volume, because of Liouville's theorem) must be fully contained within $P(B)$, so vol(P(B)) > vol(P(A)).
A: So, the short answer is that you're quite correct: if the dynamics of a system is subject to Liouville's theorem, then phase space volume is conserved, so the entropy associated to a given probability distribution remains constant as it evolves under those dynamics. This is actually just one instance of a much more general puzzle: how do we reconcile the irreversibility of thermodynamics with the reversibility of classical mechanics (if we are seeking a way of "reducing" thermodynamics to classical statistical mechanics)? The literature on this puzzle is huge. If you're interested, a good introduction is "Time and Chance", by David Z Albert.
In terms of how this is handled in practice, the answer is (as Ross Millikan says) that we use processes of coarse-graining or projection, exploiting the fact that the probability distribution spreads out into filaments. Again, the details of this process (and its conceptual significance) are somewhat involved. Good papers to look at for that are "The Logic of the Past Hypothesis" (available at http://philsci-archive.pitt.edu/8894/) and "What Statistical Mechanics Actually Does" (http://philsci-archive.pitt.edu/9846/), both by David Wallace.
A: Liouville's theorem says the accessible volume in phase space does not increase, but it tends to become narrow filaments that "fill up" a much larger volume.  If you think of a particle in a reflecting box, you might start it with a known position $\pm 1$ mm in all three axes and a known velocity $\pm 1$ mm/sec in all three axes.  This is a phase space volume of $64$ mm^6/sec^3.  If you follow the evolution of lots of points within the starting volume, they will scatter throughout the box at various velocities.  After enough time, the particle can within $\pm 1$ mm of anywhere in the box with a range of velocities.  When we look at the entropy at a later time, we spread all of these together, so we say the particle can be in the whole volume of the box at any of a range of energies.  That gives a much higher entropy.  If you found the exact regions of phase space the particle could be in the volume would not have increased, but the smearing out has made the volume increase and with it the entropy.
A: This is a very interesting question. I have often asked myself this question and found a good answer first by reading Prigogine's works on non-equilibrium thermodynamics. He outlines this paradox and focuses mostly on the microscopic processes. Microscopic processes might be reversible or irreversible. If all microscopic processes are reversible, then the system is not able to produce entropy. In this case Liouville's theorem is fulfilled, the phase space stays at the same volume all the time. The problem is, by perceiving our universe, we realize that there is such a thing as increase in entropy. The second law of thermodynamics must allow for entropy increase. Therefore a paradox exists, as in another answer here already named as ergodic paradox, or mostly referred to as "Loschmidt's paradox".
So comparing this problem to a billard table (without holes), the balls represent the particles and once pushed, a ball rolls over the table, making collisions with other balls, transferring momentum and so on. If all processes on this table are reversible, the system will never go back to the quiet state, with all balls resting. There will always be a rolling ball, thus phase space will remain at the same volume. In contrast a specific resting configuration is a single point in phase space. The whole dynamics change, once irreversible processes are allowed. If these irreversible processes are all according to the 2nd law of thermodynamics, then the balls will come to rest after finite time. This is actually what we perceive in reality. So a quite easy solution is to introduce elementary particle processes, which are not completely reversible. Unfortunately whenever physicists unveil the dynamics at these time scales, all processes are found to be reversible. What is fission of an atom, seemingly an irreversible process, becomes an interaction of smaller particles, neutrons and protons, if one looks closer. These smaller particles then interact with each other just using reversible processes, thus offering a description without irreversible processes. One can then raise the hand and say "What is with CP violation?", Ok good objection, but when one looks at CPT-symmetry, the reversibility is restored. So even going to quantum mechanics, does not help. Because there is Liouville's theorem even in quantum mechanics, it is called Von-Neumann-equation. Still we know, that entropy increases when wave functions collapse (or at least stay the same, if the density matrix does not change). Prigogine stays classical and does not discuss the quantum aspects of this paradox, but he offers a solution for the classical version. He basically says, that the idea of elementary particles is flawed. If you assume elementary particles exist, and elementary means, there is no irreversible process, which breaks them up into smaller particles, then Liouville's theorem becomes true. Because describing a model world with particles that only obey reversible processes conserves phase space. But the concept of elementary particles might be a human concept and nature can produce an infinite number of "new particles", if necessary. What is elementary then, is not particles, but rather irreversible processes.
This is why Prigogine starts his book "From Being To Becoming" with a quote from Goethe: 
"Komm, drücke mich recht zärtlich an dein Herz!
Doch nicht zu fest, damit das Glas nicht springe!
Das ist die Eigenschaft der Dinge:
Natürlichem genügt das Weltall kaum;
Was künstlich ist, verlangt geschloßnen raum."
In english (if someone has a better translation, please post it :D)
"Come, press me gently to your heart!
Not too firm, so that the glass does not break!
This is the characteristic of things:
For natural things the space is not enough;
Only the artificial needs closed space."
