Columbus is traditionally (and indeed still) credited with the discovery of the Americas for a number of reasons, some dubious but others quite legitimate. First of all, we must qualify this discovery as discovery by Old World people. Clearly, the original "discovery" by the human species was some 40,000 years ago by the ancestors of the indigenous populations of North and South America, but given that this original settlement was well within the pre-historical period, and that there has probably been no contact between the peoples of the Americas and the Old World (specifically Asia) in the last 10,000 years, it might be said that we implicitly mean a "re-discovery" (within the historical era) of the Americas.
Wikipedia actually has a fairly well-written paragraph on the subject:
Though Columbus was not the first European explorer to reach the Americas (having been preceded by the Norse expedition led by Leif Ericson), Columbus' voyages led to the first lasting European contact with America, inaugurating a period of European exploration and colonization of foreign lands that lasted for several centuries. They had, therefore, an enormous impact in the historical development of the modern Western world. Columbus himself saw his accomplishments primarily in the light of the spreading of the Christian religion.
Also worth noting is that Columbus led four expeditions to the New World: the first landed on the island of Hispaniola, and others ventured to Cuba, mainland Central America (Mexico area), and the northern coast of South America. Indeed, there is no doubt/controversy that Columbus was the first historical person of the Old World to discover South America.
Over the past few decades there has been some talk and a beginning of tre acceptance of the theory that the Solutrean peoples of southern France/northern Spain made it across to North America on small boats some 20,000 years ago, by navigating the iceburg-ridden North Atlantic ocean. While lying chronologically after most of the waves of migration from East Asia into North America, it is still within the pre-historical period and hence is not usually considered in this discussion -- not least, due to its non-universal acceptance at present.
Now, the first matter is that there exists clear historical evidence (both archaeological and written) that the medieval land the Vikings called Vinland does indeed correspond to Newfoundland, eastern Quebec, and the northern parts of New England. This occurred some time in the late 10th century A.D. (reputably by Leif Ericsson and his crew) when they were forced off course en route to Greenland and landed in Newfoundland. A number of reasons can be given for the diminished importance of this re-discovery, as follows.
The discovery was virtually lost into Viking legend during the following centuries, when the successor states of the Viking homeland (Denmark and Norway) were forged and the Age of Migrations came to a close. As far as I know, conclusive evidence for the Norse discovery only came to light during the 20th century.
The Vikings never made a permanent settlement in North America. At best, they explored around a bit, sailing up some of the major rivers (perhaps even the Hudson), and doing some minor trading with the Native Americans. However, there is no reliable evidence for routine trading with the North Americans, and indeed there are sources suggesting the Vikings considered them to be an inferior people, suggesting most contact with them was probably in the form of skirmishes.
Despite the small inroads made by the Norseman, the discontinuation of any exploration or settlement efforts meant that the long-term relevance of their excursion into North America was of rather little significance. The Spanish discovery and the colonisation, on the other hand, had enormous import on the world has a whole.
The Vikings as a people did not represent a particularly advanced civilisation for the time, except perhaps in warfare. They were not well-educated, and most of the literature surviving from the Viking era is in the form of sagas and the history of kings and rulers. Indeed, it was the case for many years that historians found it quite difficult to separate fact from fiction due to the nature of historical Norse texts.
Now, while Columbus' discovery of the Americas (specifically of the island of Hispaniola) was no more intentional than the Vikings', it did however lead to permanent colonisation, settlement, political and economic expansion of the lands of the Americas by Spain, then Portugal, and finally other European nations. It really comes down to the import of the discovery on socio-political world affairs, which was huge in Columbus's case.
Of course, there have been other rumoured (re-)discoveries of the American continents in historical times, but none with conclusive historical proof, or even a substantial level of acceptance by modern historians. These include rumoured and highly controversial discoveries by the Phoenicians, the Roman Empire, the Israelites, and the Yuan Dynasty of China, as you suggest.
So in conclusion, given the importance of the two verifiable and widely acceptable discoveries of the Americas in modern time, it is not too inaccurate to say that Columbus discovered America. I personally would be quite happy if people said "Columbus discovered central America". To qualify this statement properly, one should really say "Christopher Columbus and his crew were the first people of the Old World during the historical to make a discovery of the Americas that had macro-historical importance." Well, you get the assumptions. Most people unfortunately probably do not realise these assumptions, though I do not think that totally invalidates the statement. Given the proper implicit qualifications, I do believe it is only fair to give Columbus credit for his great skills and daring as a navigator and explorer during this notable period of history.