Experiments are showing that larger and larger objects can be entangled whereby proving that this quantum feature has no upper limit. Assuming this is true, does entangled celestial bodies mean even the 2-Body and not just N-body problems are also unsolvable?
Quantum mechanics it the underlying layer of Nature at the microscopic level, its effect mainly constrained to small dimensions because of the small value of the Planck constant h_bar.
There exist large dimension quantum mechanical effects, effects that can only be described by quantum mechanical equations and experiments validate the predictions.
The existence of crystals is another matter phase that requires quantum mechanical solutions.
In these, and other, examples of macroscopic manifestation of quantum effects, of which entanglement is one , the phases of the microscopic components of matter build up coherently to large dimensions. The general effect on matter as we know it is that the phases are lost: an incoherent statistical ensemble treatable with classical mechanics and electromagnetism is the usual state of matter.
When one reaches celestial dimensions it is hard to see any phases surviving in the interaction between two celestial bodies, which will be gravitational. We do not have a quantum gravity solution at the moment of the type of the Schroedinger equation so as to even imagine calculating the phases between two elementary particles under gravitation nor statistical ensembles of them, which are the celestial bodies.
Even as a thought experiment, it is not possible to check whether phases could survive on a celestial body and a quantum mechanical gravitational interaction retain its phases over celestial distances.
So no, at the moment the two body problem can be safely solved with classical theories of gravity.
That said, quantum entanglement effects are an active research for the first moments of the Big Bang where all forces are equally strong . The cosmic microwave background radiation is studied to see this effect,
but these were not celestial bodies interacting but a primordial plasma/soup.