Why isn't the 3 body problem solvable?

I'm new to this "integrable system" stuff, but from what I've read, if there are as many linearly independent constants of motion that are compatible with respect to the poisson brackets as degrees of freedom, then the system is solvable in terms of elementary functions. Is this correct? I get that for each linearly independent constant of motion you can reduce the degree of freedom by one, but I don't understand why the theorem

Theorem (First integrals of the n-body problem) The only linearly independent integrals of the $n$-body problem, which are algebraic with respect to $q$, $p$ and $t$ are the $10$ described above. (http://en.wikipedia.org/wiki/N-body_problem#Three-body_problem)

implies that there is no analytic solution (I think this is synonymous with closed-form solution, and solution in terms of elementary functions). I've been trying to think about it, but I can't reason it, and apparently integrability implies no chaos, which I can't see either.

For the classical 3-body problem, the obstacle to a solution is, as you said, integrability. This is also sometimes called separability, and when it fails, it means that there does not exist a manifold in phase space such that on that manifold, the equations for the independent degrees of freedom of the equation are separated into independent equations. This is in turn related to being able to interchange mixed partial derivatives as you mention for the Poisson brackets, because if the equations separate, derivatives (and therefore integrals) can be performed in any order.

The relationship between this and chaos is that non-integrable systems are generically chaotic -- meaning "usually" or "observably" chaotic, the obstacle to separating the degrees of freedom being that there are intersecting stable and unstable manifolds of hyperbolic periodic points which cause the solutions to fold endlessly in phase space. "Generic" has a definition here, it means true on a countable interesection of open dense sets -- in other words, for every solution, there is an open subset of solutions arbitrarily close which have this property.

Hope this helps. There is a completely worked out solution for what is called the "restricted 3-body problem" (3 body problem in which one of the bodies has no mass) in Jurgen Moser's Stable and Random Motions in Dynamical Systems, which shows that even in this case, the motion of the massless body is chaotic for most initial conditions.