The Vikings settled in greenland and on the scale of things it's only a short hop to Newfoundland, so it is likely that they knew about this landfall even if they did not make permanent settlements there. Leif Ericsson's descriptions include a word for the inhabitants - 'skraelings' - recently adopted by philip pullman in the Dark materials trilogy.
However, there are also tenuous hints that irish monks may have also made landfall in North America - see any info about St Brendan's voyages