The gravitational $n$-body problem is well known to be uncomputable; one can not find a general algorithm that works in all cases that can predict the trajectories of $n$n-bodies. However, in contrast to our inability to compute a general solution, the universe seems perfectly capable of "predicting" the trajectories of $n$-bodies. Presumably, it does this with no error, either.
How can this be? Could this be evidence that the universe is a hypercomputer?
Well, I don't think of the universe as a computer. You've hit on one of the reasons here: the complexity of simulation increases much faster than the complexity of systems. However, complex systems have no more trouble behaving physically than simple ones do. Behavior of physical objects is, in this way, profoundly different from the behavior of the mathematical abstractions we use to model them.
Two key misconceptions in the question are:
As it wanders through its phase space, the system assumes one configuration after the other. We might perhaps describe this as "calculating its next position from the current one", but here is the thing: This is something we can do as well by simple integration. We just cannot do so for the longer term, due to the system's chaotic dynamics, but then there's no reason to believe the universe is performing this long-term calculation either.
As for things we indeed can't calculate, for some cases it can be solved by changing the hardware - for instance, one of the most promising applications of future quantum computers is precisely the simulation of quantum systems. In the general case, however, Traub convincingly argues that noncomputability (in the sense of noncomputable numbers) shouldn't pose a problem to physics and the case of intractability (a concept closer to the OP's) remains an open problem.
Related questions:
Is Physics Computable?
Is the universe a Turing machine?
Computation theory and the simulation argument
What are the consequences of a non-computable universe?
The main issue - and difference - between the $N$-body simulations that we are capable of running on computers and the gravitational interactions in the real universe is that we discretise time into a series of time-steps in order to "step" the simulation forward.
On the other hand, in the universe, time is continuous, and is not "chopped" up into intervals of any kind. The movement of bodies is continuous through space. Therefore, when two or more bodies are interacting under gravity somewhere in the cosmos, the force - and, therefore, acceleration - experienced by each body at every moment in time changes continuously with their changing position.
In our $N$-body simulations, however, since time is discretised into a series of steps, the movement of bodies is approximated by only evaluating the forces on bodies at the beginnings and ends of time-steps. The consequence of this is an error in the precise positions (and velocities) of the bodies, since the force on the bodies was not evaluated at the infinitely many points between the times $t_n$ and $t_{n+1}$, when the force was actually changing (and so the effect of these changing forces was not reflected at all in the positions and velocities of the bodies between $t_n$ and $t_{n+1}$).
Of course, there is little that can be done about this, since, although the size of the time-step, $\Delta{t}$, can be made arbitrarily small (albeit at the cost of computation speed), it will still be infinitely larger than zero, and thus errors will always begin to accumulate.
On top of this, as you have alluded to, there is no closed-form, analytic solution to the general $N$-body problem (for $N>2$) - hence why we resort to numerical methods - so, for now, we are stuck with our current simulations! That being said, a lot of them are extremely accurate and/or impressive in the amount of bodies they can evolve based on a variety of different integration methods and/or force approximation techniques.
