Is it possible to use different locations for the colonists/explorers? Or would that be ASB?
There are three different "routes" along which the discovery of the Americas is likely.
i) The "sail as far West as you can to try to reach Asia" trade wind route that Columbus tried. It ends up in the Caribbean region. A good place for sugar plantations and eventual conquest of Mesoamerica.
ii) The Northern route that the Vikings and John Cabot took ending up in the Newfoundland area. Great for fishing, but not so great for colonies.
iii) The accidental discovery of Brazil while heading South towards the tip of Africa (which happened due to the volto da mer (sorry about the bad spelling)). Colonies in Brazil make sense both as stopovers on the way to the Southern tip of Africa, but also as plantation regions.
In OTL, if we discount the Vikings, i) was discovered first, followed by ii) and then iii), and they all happened within a decade of each other. ii) could easily be exploited first if knowledge of the Vikings' voyages survives long enough to inspire 15th-century explorers. Alternately, iii) could result in the first discovery of the Americas if the Southern route to Asia is considered more promising than the hypothesized Western route. None of these POD's would be ASB, provided that you gave enough explanation as to WHY Columbus' voyage didn't happen as OTL.
Alternately, you could have explorers follow the same routes as OTL, but have them be sponsored by different countries. Maybe Portugal rather than Spain hires Columbus, or Cabot is sponsored by France. In such a situation, again, it would not be ASB as long as there is an explanation of WHY Spain decided not to go with Columbus.
Later, of course, there's lots of room to play with in the sites of exact settlements. The first areas to be colonized OTL were generally the easiest to get to. You would likely see colonization attempts in the Caribbean and Eastern Canada before the East coast of the US just because those spots were more easily accessible. Although, you could definitely have the first colonies fail, thus making the first successful colonies happen elsewhere....