Columbus was not, in fact, the first to cross the Atlantic. There were Norse communities living in Greenland from the 10th Century. They even had some temporary settlements in North America proper. However, the Norse weren't as good at eking out a living in the North Atlantic as the Inuit, and (after 500 years) eventually got wiped out by some combination of their attacks and climate change.
However, this was far before the printing press, and at the extremes of European settlement, so it wasn't well-known in Europe.
There are several other tales of possible transatlantic crossings. However, none of them left the physical evidence behind that the Vikings did, so they are all generally regarded as just tales.
To be fair, we should also note that Inuit peoples regularly crossed to America from Asia, as did all the other indigenous peoples of the Western Hemisphere at some point. The island chains between Siberia and Alaska aren't all that much of a barrier for people used to living in that ecosphere. There is also indirect evidence of Polynesian contact with South America across the tropical Pacific.
What was important about Columbus was not his primacy. It was that when he came back, all of Europe (and probably the educated all over the Old World eventually) heard about it in detail, thanks to the recently invented printing press. Additionally, the society he came back to had both the means and the motivation to follow up. This is what the Norse, and the folks behind any other tall tales of Atlantic crossings that may happen to be true, did not have.