One of the great unsolved problems in physics is turbulence but I'm not too clear what the mystery is. Does it mean that the Navier-Stokes equations don't have any turbulent phenomena even if we solve it computationally? Or does it mean we simply don't have a closed-form solution to turbulent phenomena?
Turbulence is indeed an unsolved problem both in physics and mathematics. Whether it is the "greatest" might be argued but for lack of good metrics probably for a long time.
Why it is an unsolved problem from a mathematical point of view read Terry Tao (Fields medal) here : http://terrytao.wordpress.com/2007/03/18/why-global-regularity-for-navier-stokes-is-hard/
Why it is an unsolved problem from a physical point of view, read Ruelle and Takens here : http://www.ihes.fr/~ruelle/PUBLICATIONS/%5B29%5D.pdf
The difficulty is in the fact that if you take a dissipative fluid system and begin to perturb it for example by injecting energy, its states will qualitatively change. Over some critical value the behaviour will begin to be more and more irregular and unpredictable. What is called turbulence are precisely those states where the flow is irregular. However as this transition to turbulence depends on the constituents and parameters of the system and leads to very different states, there exists sofar no general physical theory of turbulence. Ruelle et Takens attempt to establish a general theory but their proposal is not accepted by everybody.
So in answer on exactly your questions :
yes, solving numerically Navier Stokes leads to irregular solutions that look like turbulence
no, it is not possible to solve numerically Navier Stokes by DNS on a large enough scale with a high enough resolution to be sure that the computed numbers converge to a solution of N-S. A well known example of this inability is weather forecast - the scale is too large, the resolution is too low and the accuracy of the computed solution decays extremely fast.
This doesn't prevent establishing empirical formulas valid for certain fluids in a certain range of parameters at low space scales (e.g meters) - typically air or water at very high Reynolds numbers. These formulas allow f.ex to design water pumping systems but are far from explaining anything about Navier Stokes and chaotic regimes in general.
While it is known that numerical solutions of turbulence will always become inaccurate beyond a certain time, it is unknown whether the future states of a turbulent system obey a computable probability distribution. This is certainly a mystery.
Turbulence is not one of the great unsolved problems in physics. Physics tells us exactly how turbulence emerges as a direct consequence of local mass and momentum conservation. We can create multiparticle computer models such as lattice gas automata that generate turbulence at large length and time scales. We can write down the equations that govern turbulence. These are the Navier-Stokes equations.
From a fundamental physics perspective, turbulence is a solved problem that has entered the engineering realm a long time ago.
So what is the unsolved problem associated with turbulence? In short, turbulence is an unsolved problem not in physics but in mathematics. The point is that mathematicians struggle to answer the question if the Navier-Stokes equation always allows for solutions that at fine enough length and time scales are well behaved. In fact, if you manage to conclusively answer this question ("yes" or "no"), you will win a math prize that comes with a handsome cheque of $ 1,000,000.
In case you want to give it a try, the precise question is:
The math difficulties have to do with the fact that turbulence emerges when the highest derivative term in the Navier-Stokes equations (the viscosity term) becomes small compared to the other terms. You can take almost any non-linear partial differential equation, and get mathematicians to cringe simply by multiplying the highest derivative term with a factor $\epsilon$ and ask about the limiting behavior of the equation when $\epsilon$ approaches zero.
Fundamental physicists shrug and continue studying real mysteries such as quantum gravity.