I don't think it would have ended up changing history too much, other than specifics of nation names, I think in the end European colonization over Native Americans would have been very similar in results. Massive slavery, disease, destruction, forced conversion, etc.
"History might not repeat itself, but it sure does rhyme" would be how this ATL would develop. Remember that the Spanish conquests and rule was not much different than a transportation of Medieval feudal land ownership. Even the Dutch attempted a semi-feudal landownership scheme in New Netherland in the 1600s, with Rensselaerswyck, et al.
While i agree on the economic side, i don't know, the notion of nation state and monarchic absolutism are not present in the Middle Ages. The cultural paradigm in the XII-XIII centuries, for example was the one of the Christian Empire, and of the Papal supremacy over secular rulers.
I think that, given the opportunity to colonize America say, in the XII century (assuming ocean faring technology), we will see a different pattern in colonization:
-pre-eminence of christian missions once civilization is found: what's the first thing to do, in the middle ages, when you find a pagan land? Christianize, of course, and given the decentralization of such maritime adventures (medieval monarchies are not complex or centralized enough to have a say in this), maybe with aristocratic capitals and merchants' fleets, and the lower military sophistication (middle ages tactics vs renaissance ones?). While technology is not that different, military tactics are the real change.
-demographics: while in the XVI-XVII centuries the colonists were from the persecuted social strata, in the high middle ages we will see peasants and cadets making their way to the only thing that mattered at the time: land. Once natives are found, the Papacy would be fast to declare another crusade, like it did in the Baltic. This is important, because you would probably butterfly away the XIV centuries famines and maybe even the Black Death. This means a slower rise of the middle class and a longer feudal lords' hegemony on the lower classes.
While i agree with your "I don't think it would have ended up changing history too much, other than specifics of nation names, I think in the end European colonization over Native Americans would have been very similar in results", you should consider that Natives treatment would be at least moderately imperialist, instead of the Native-screw of OTL, because of the logistical difficulties listed above.
Also, opening the Atlantic in the high middle ages would make the decline of the Mediterranean trade pre-eminence slower. In the end, you would get a slower/earlier Renaissance (just another way to spell "Rise of Europe").
And, if Byzantium dies slower (if it even dies at all), or the Crusades manages to get Egypt (unlikely, but who knows, maybe the fourth crusade goes straight to Egypt?), and thus access to the Red Sea, you would have the Italian maritime-republics on steroids (Venetian Cyprus, just think about it).
A much more interesting world, on the cultural side. Crusader-ideals survive longer, and the medieval ideals would face a slower death, and thus would be more rooted. I'll stop here, before spewing too much ASB
