More can always be said, but /u/partymoses and myself have addressed the topic here. The TL;DR version is that the news of Columbus' findings travelled extremely fast, thanks to the publication of his letters in popular, cheap books that historians call "occasionals". However, what he had actually found remained murky for a while. While European leaders understood that there was something promising there, for the general population it was hardly different from fantasy. The idea that this was a "new world" emerged after Amerigo Vespucci's own travels and it took several decades before the concept of "America" as a separate land mass became accepted by the general public.