It was around before that
This is not the first finding, though this one is probably the best preserved one. I have seen various articles on this as far back as 20 years ago.
Syphilis was around before Columbus, but not as prevalent as during the 16-17th century for a completely different reason. A lot of late stage 2 and stage 3 syphilis symptoms are similar to the symptoms for leprosy. As result in the early middle ages most syphilitics ended up in the leprosy hospices. These were run by the church (Dominicans if memory serves me right).
A pope edict closed down the church run leprosy hospices shortly before the first expedition by Christopher Columbus. As a result along with leprosy stage 2 and stage 3 syphilis sufferers were thrown out onto the streets to fend for themselves including resorting to the "oldest profession". The rest as they say is history.