Integrable vs. Non-Integrable systems Integrable systems are systems which have $2n-1$ time-independent, functionally independent conserved quantities ($n$ being the number of degrees of freedom), or $n$ whose Poisson brackets with each other are zero.
The way I understand it, these conditions correspond directly to us being able to do the Hamilton-Jacobi transformation, which is roughly equivalent to saying that the $2n-1$ conserved quantities are the initial conditions of the problem, which itself is a way of saying that the map from the phase space position at some time $t_0$ to that at time $t$ is invertible.
But, if the last statement is right, why are there systems which are non-integrable at all? Shouldn't all systems' trajectories be uniquely determined by the equations of motion and initial conditions? Or is it that all non-integrable systems are those whose Lagrangians can't be written (non-holonomic constraints, friction etc)?
I've heard that Poincare proved that the gravitational three-body problem in two dimensions was non-integrable, but he showed that there were too few analytic conserved quantities. I don't know why exactly that means non-integrability, so if someone could help me there that would be great too.
 A: Complete integrability is far stronger than solvability of the initial value problem.
Complete integrability implies the absence of chaotic orbits. More precisely, all bounded orbits are quasiperiodic, lying on invariant tori. Perturbations of a completely integrable system preserve only some of these tori; this is the KAM theorem.
http://en.wikipedia.org/wiki/KAM_theorem
The three body problem may have chaotic orbits, hence is not completely integrable. But it is easy to write down its Lagrangian.
A: There are systems which are not integrable (in Poincaré sense) because interactions destroy the invariants. Consider a Hamiltonian $H = H_0 + \lambda V$, where $H_0$ is the unperturbed Hamiltonian and $\lambda$ the coupling constant. If you start with the interactions turned off you can find invariants of motion $\Phi^0$ by the usual Poisson bracket
$$\{H_0, \Phi^0\}=0$$
If the system is integrable we can find a new set of invariants $\Phi$ which are analytic in the coupling constant and satisfy
$$\{H, \Phi\}=0$$
when interactions are turned on. An example are the generalized momenta obtained from the Hamilton-Jacobi equation (as you correctly note). 
But if the system is non-integrable (in Poincaré sense) then there is not such invariants $\Phi$, except energy [*]. For such systems there are not trajectories (infinitely close points in phase space diverge in time due to Poincaré resonances). Check details on Poincaré resonances and the limits of trajectory dynamics and references cited therein.
[*] Expand $\Phi$ in a Taylor series $\Phi = \sum \lambda^{(n)} \Phi^{(n)}$ and expand each $\Phi^{(n)}$ in a Fourier series. The bracket $\{H, \Phi\}=0$ transforms into $\{H_0,\Phi^{(n)}\}+\{V, \Phi^{(n-1)}\}=0$. It can be shown that this is equivalent to the vanishing of the Fourier coefficients $\phi_{k}^0=0$ for any wave vector $\mathrm{k}$. Precisely non-integrable systems  (in Poincaré sense) are systems for which $\phi_{k}^0 \neq 0$ at resonances, thus destroying the invariants.
A: Let there be given a $2n$-dimenional real symplectic manifold $(M,\omega)$ with a globally defined real function $H:M\times[t_i,t_f] \to \mathbb{R}$, which we will call the Hamiltonian. The time evolution is governed by Hamilton's (or equivalently Liouville's) equations of motion. Here $t\in[t_i,t_f]$ is time.


*

*On one hand, there is the notion of complete integrability, aka. Liouville integrability, or sometimes just called integrability. This means that there exist $n$ independent globally defined real functions 
$$I_i, \qquad i\in\{1, \ldots, n\},$$ 
(which we will call action variables), that pairwise Poisson commute,
$$ \{I_i,I_j\}_{PB}~=~0, \qquad i,j\in\{1, \ldots, n\}.$$

*On the other hand, given a fixed point $x_{(0)}\in M$, under mild regularity assumptions, there always exists locally (in a sufficiently small open Darboux$^1$ neighborhood of $x_{(0)}$) an $n$-parameter complete solution for Hamilton's principal function
$$S(q^1, \ldots, q^n; I_1, \ldots,I_n; t)$$ 
to the Hamilton-Jacobi equation, where 
$$I_i, \qquad i\in\{1, \ldots, n\},$$
are integration constants. This leads to a local version of property 1.
The main point is that the global property 1 is rare, while the local property 2 is generic.
--
$^1$ A Darboux neighborhood here means a neighborhood where there exists a set of canonical coordinates aka. Darboux coordinates $(q^1, \ldots, q^n;p_1, \ldots, p_n)$, cf. Darboux' Theorem. 
A: This is not a complete answer, but I thought it an interesting enough fact to post here.
Even if, as you say, "the map from the phase space position at some time $t_0$ to that at time $t$ is invertible", the system may still be chaotic.  An example of this is the Hénon map,
$x_{n+1} = 1 - ax_n^2 + y_n$
$y_{n+1} = b x_n$
which for certain values of the parameters (e.g., $a=1.4$, $b=0.3$) is chaotic, and yet (except when $b=0$) is invertible:
$x_n = \frac{y_{n+1}}{b}$
$y_n = \frac{y_{n+1}}{b} - 1 - \frac{a}{b^2}y_{n+1}$.
