Unless you have an infinite amount of data any estimator only provides an "estimate" (an approximate measurement) of any parameter (such as covariances).
For the Markowitz Problem, the seriousness of the issue was realized as soon as 1974: Barry, C.B. "Portfolio Analysis under Uncertain Means, Variances and
Covariances",Journal of Finance, 1974. The problem arises because the number of covariances to be estimated tends to be large compared to the number of observations available (for example with 500 stocks you have 125,250 covariances to be estimated, but since 1929 there have only been 1056 months of stock market data). As a result each element of the estimated matrix is highly uncertain (this can be shown theoretically as well as empirically).
Two somewhat more recent references on this problem are Broadie
“Computing Efficient Frontiers with Estimated Parameters”,
Annals of Operations Research, 1993 and Chopra and Ziemba "The Effects of Errors in Means, Variances and Covariances on Optimal Portfolio Choice",
Journal of Portfolio Management, 1993. In a word, the effect is drastic, with very different optimal portfolios found if the inputs vary a plausible amount. A technique called the Resampled Frontier by Michaud can be used to illustrate the problem by solving the Markowitz problem over and over with the covariance matrix perturbed at random by a judicious amount.
Attempts have been made to come up with alternatives to the "traditional estimator". The main one is the Bayes Stein estimator Jorion "Bayes-Stein Estimation for Portfolio Analysis", Journal of Financial and Quantitative Analysis, September 1986. There are also Factor Models of the covariance. All these solutions attempt to impose some structure on the covariance matrix instead of attempting to estimate each entry independently.
In addition to this, there is also the problem mentioned by Eduardo that the covariance matrix may change due to changes in the economy. But the "estmation problem" for large covariance matrices is serious even in the absence of long term economic changes.