What are the primary obstacles to solve the many-body problem in quantum mechanics?

First let me start by saying that the $N$-body problem in classical mechanics is not computationally difficult to approximate a solution to. It is simply that in general there is not a closed form analytic solution, which is why we must rely on numerics.

For quantum mechanics, however, the problem is much harder. This is because in quantum mechanics, the state space required to represent the system must be able to represent all possible superpositions of particles. While the number of orthogonal states is exponential in the size of the system, each has an associated phase and amplitude, which even with the most coarse grain discretization will lead to a double exponential in the number of possible states required to represent it. Thus in quantum systems you need $O(2^{2^n})$ variables to reasonable approximate any possible state of the system, versus only $O(2^n)$ required to represent an analogous classical system. Since we can represent $2^m$ states with $m$ bits, to represent the classical state space we need only $O(n)$ bits, versus $O(2^n)$ bits required to directly represent the quantum system. This is why it is believed to be impossible to simulate a quantum computer in polynomial time, but Newtonian physics can be simulated in polynomial time.

Calculating ground states is even harder than simulating the systems. Indeed, in general finding the ground state of a classical Hamiltonian is NP-complete, while finding the ground state of a quantum Hamiltonian is QMA-complete. (On the other hand, ground states are to some extent less relevant because the systems for which is is computationally hard to calculate the ground state of (at least on a QC) don't cool efficiently either.)


The answer is fairly simple -- classical N-body problem has its solution in $6N$ 1D functions of time, quantum N-body problem has its solution in one complex function, but $3N$-dimensional (not counting spin and similar stuff). Then, there is no wonder why one can find analytical solutions only for trivial problems or at least make $N$ huge and escape into statistical mechanics. And yes, this is only the problem of mathematical complexity here.
From modelling point of view exact solving also seems hopeless, with only memory complexity of $\mathcal{O}(K^{3N})$.

For the rest of the answer I will restrict myself to quantum chemistry/material science, since this is the most exploited region -- this means we are now talking about atoms. First of all, atoms have small and very heavy nuclei, which thus can be treated as almost stationary sources of electrostatic potential; this reduces the problem to electrons only (Born-Oppenheimer approx.). Now, there are two main routes to follow: Hartree-Fock or Density Functional Theory.
In HF, one roughly represents the many-body weavefunction as a combination of some standard base functions -- then one can optimize their contributions to get minimal energy, yet using extended Hamiltonian to adjust the effects of such approximation. In DFT, one encouraged by Hohenberg-Kohn theorems reduces the many body weavefunction to electron probability density field (3-dimensional), and accordingly Shroedinger equation terms into density functionals (and there approximations are applied). Next, it can be either solved as this 3D field or in Kohn-Sham way, which is pretty much Hartree-Fock for DFT (one represents density with base functions). People sometimes are making something analytical here, but those are mostly theories made to support computational approaches.

And finally your last question: those approximate methods (but still ab initio -- there are no experimental parameters there) do predict things like chemical reactions, various spectra and other measurable quantities; accuracy is problematic though. Biology is mostly out of reach because of a time scale; at least there are hybrid methods able to mix for instance the classical simulation of protein motion with quantum simulation of the binding site when it is squeezed enough so something quantum like enzymatic reaction can take place.


In addition to what mbq said, it might be interesting to know that things get really funny in relativistic quantum mechanics, that is using the Klein-Gordon and the Dirac equation (but without the "second" quantization of Quantum Field Theory). There, there's one wave function per particle sort, so no matter how many particles of one kind you consider, the only thing that changes is the field itself. You only get more degrees of freedom by actually adding another kind of particles. Of course, since Fermions require Spinors, you may end up with other computational issues then...