The French blamed the English and the English blamed the French, but apparently Columbus really did bring syphilis home with him from the New World. Scientific American reports:
A new study provides what scientists say is the most convincing evidence to date that the Italian adventurer and some of his crew contracted the disease during their voyage to the New World—and unwittingly introduced it to the old one circa 1493.
The great pox was not a fair exchange for the small pox, though, which came west in the early 1500s. According to the seminal demographic research of the Incas by Henry Dobyns:
. . . smallpox arrived around 1525, seven years ahead of the Spanish [arrival in Peru]. Brought to Mexico apparently by a single sick Spaniard, it swept south [north as well, of course -- GH] and eliminated more than half the population of the Incan empire. Smallpox claimed the Incan dictator Huayna Capac and much of his family, setting off a calamitous war of succession. So complete was the chaos that Francisco Pizarro was able to seize an empire the size of Spain and Italy combined with a force of 168 men.
For more information on the incredible research that has reshaped the way scholars think about the pre-Columbian and transitional Americas, read Charles C. Mann's fascinating book 1491.