How is Liouville's theorem compatible with the Second Law?

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.

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.

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.