The effects may not be as dramatic as one might think at first glance. Columbus was sailing west following up on existing rumours of land sightings by Portuguese sailors off Africa, who had caught sight of Brazil. If he doesn't return, men will dismiss his theory of a small earth with a near Japan across the Atlantic as hogwash (which, in fact, it was) but America will still be found and explored a few years later, and possibly colonised (though more tentatively if no one thinks it's the lucrative East Indies at first).
However, importantly, this exploration and colonisation might be done by someone else, with Spain a latecomer to the table.
And, if Portugal has a current monopoly on Asian trade to the east, once South America is discovered to be big, somebody, maybe England, will want to explore this strange new continent. Is this plausible (below)?
1500: Cabral sights Brazil, but does not land (butterflies at work here; he doesn't expect anything of particular interest here).
1501: Cabral returns to Brazil, and discovers it to be a continent. He returns to Portugal after sailing as far south as the Rio de la Plata and encountering the threat of mutiny. The English hire John Cabot, who visits South America and the Caribbean.
1502-1506: More English explorers visit the New World. They encounter the remains of Columbus's ill-fated expedition. The Portuguese are more interested in the East, however, although they do hold Brazil.
1507: The English discover Chesapeake Bay by sailing more directly west than they have been up to this point. The Treaty of Lisbon divides the New World between Portugal and England at the equator.
(Note that Peru is in the southern hemisphere, in Portuguese territory, although the English are probably going to get there first...)
This isn't really very refined, but I need to get to bed. What do you think?