The people on the alternate history boards have speculated on what the rest of the world looks like. I haven't spent too much time on that, because as White wrote
"In most of the world, the New Middle Ages were merely a rerun of the Old Middle Ages. In England and Japan, the constitutional monarchies dumped their constitutions. Europeans turned again to the Roman Catholic Church for guidance. Camels plodded along the caravan routes of the Middle East, bringing silk from China and pilgrims to Mecca, just as they did a thousand years ago"
It should be reiterated that medieval America is amazingly unique. So in much of the Old World, there would not be many changes. Maybe some states, or languages we didn't see from 1000-1500, maybe even new world crop or two made it over, but somebody from then would recognize this world. The knights and castles of Europe, the empires of the east. Africa would also likely resemble its pre-modern period, as people don't realize how sophisticated Africa was before it got plundered for slaves and resources. Spain, Russia, and Japan might stretch the confines of "medieval", as they would probably be more like their 1500 selves than anything, but still in that zone. Perhaps the hardest bell to unring would Australia, although even then, with its size and climate resembling places like California and Texas, would not be more than three million at the most. Also, it would be unrecognizable as Australia, because it would be so isolated from the rest of the Western world. But between the completely alien and the back to basics would be Latin America.
It should be said Latin America may not even be applicable as a concept. Spanish and Portuguese are definitely unlikely to be spoken in vernacular at this point, although the Catholic Church, depending on how prominent could possibly throwback to Latin as a means of communication, keeping all the nations roughly in the Romance language sphere. Thus, Latin America could conceivably mean "Catholic America". This would be very interesting, since it's hinted many Caribbean Islands now practice Voodoo. The Caribbean is already a mix of Spanish, French and English speakers, and its largest Latin American nation, Cuba, is relatively irreligious, so, perhaps like the west coast, would be rife for mass conversions. Thus the Caribbean would probably not be considered Latin America in any sense, although that's still four million or so people at the most.
We do know that upper Mexico is Catholic, and this would be the deserts that are fairly isolated and border the former United States, so I think it would be fair to assume the the Catholic influence only intensifies as we go to the core of the country. The that ranges from Mexico to Colombia and South America is known as "The Spanish Main", and it is the oldest colonized region of North America, starting back from the early 16th century. As a result, it's not too far removed from the Middle Ages, and thus Colonial Mexico probably does not look dissimilar from how it looked back then. If anything, the resemblance might be closest to late antiquity, with governors or viceroys administering on behalf of a distant monarch. Of course, there is no distant monarch now, and with the reemergence of the Church, which owned most of the land in the original colonial period, as a stabilizing force, there's definitely reason to believe a neo-Medieval period wouldn't be too different from its colonial period.
The western part of South America may even more strongly resemble its 16th century counterpart. The last time the U.S. had a population equal to that of Medieval America, it was the 1880's. The 1880's also saw the former nations of the Inca Empire reach the population it had at the Inca's zenith, so overall, this looks to be a pretty good model for New World medieval countries. While we would not see a reborn Inca empire, the topography of Peru and its neighbors prevented the conquistadors from taking too heavy a hand when governing or transforming the culture. Quechaun is the most widespread Indiginous tongue, and so one can easily see that being the common populace's language, while a Latin warrior class rules over them. Not so different from say, Norman-conquered England.
I would believe that interior South America, particular the Amazon would revert to as much pre-Colombian tribalism as possible. Even the industrial age was never able to make inroads into the Amazon basin, and it would only be more difficult without machines or guns or infrastructure.The Guyana area was always underpopulated anyways.
The most radical change would be on the Southern Cone--Brazil, Argentina, Uruguay. This is were the Native population never really recovered or intermarried with the settlers, or were even around in the first place. This is also the "breadbasket" of Latin America, so we're looking at a strong agricultural product.