I think a butterfly from a failed or smaller Roman Empire could be continued nautical innovation among the Atlantic Celts, which could see them get the technology to to colonize the North Atlantic earlier than OTL from Britain.
Due to the early nature of the POD and the lack of written historical record, it's a little hard to say specifically what these settlements would look like and what cultural changes will drive them. Perhaps a lack of Roman conquest in the British Isles results in a high population, and we see people emigrating looking for farmland. Perhaps a monastic religion like Buddhism or an alt-Christianity takes root eventually in Northern Europe, which sees monks looking for isolated land on which to create abbeys and hermitages.
If you have the technology to jump to southern Greenland, you have the technology to reach Newfoundland. Of course, the trip would be very dangerous and would be made rarely or only with dire necessity. I can see the need to gather timber becoming important for an alt-Greenland colony, and without the economic pressure to harvest walrus ivory as tribute for the Catholic Church, more resources and time may be spent on going to the New World for timber than IOTL.