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.
2-Body Problems also exist which have no specific solution such that there is a range of solutions for a given physical condition.  This means solvability is not based on the number of bodies but the state and representation of space.

Indian Journal of Science and Technology published a physical proof called, “Binary Precession Solutions based on Synchronized Field Couplings”  

http://www.indjst.org/index.php/indjst/article/view/30008/25962

In this research, a generalized wave function with classical characteristics was isolated within the motion of binary stars.  The wave function provided the first tool for cracking the complex motion of DI Herculis and other binary stars that had several measured precession solutions. 

http://xxx.lanl.gov/pdf/1111.3328v2.pdf

In this research, published about a year after the Indian Journal of Science and Technology publication, mathematicians from Imperial College London produced a proof for the physical existence of wave functions.  The research was published in Nature Magazine.