After the Jewish War, many Jews were deported to Italy, and there had been Jews in Rome before that. Jews may have migrated to Italy from other European countries in the Middle Ages. So Columbus could belong to a Y-DNA haplogroup characteristic of Jews without having recent Jewish ancestry.
Because of conversions, forced or otherwise, in the Middle Ages, can anyone of European ancestry say definitively that they have no Jewish ancestors? It could be someone 10 or 20 generations back but still an ancestor.
Interesting reading at Goog Books The Wife of Columbus.
As to the allegations, there was converso-ism before the 15th century but certainly nothing like the way it got going on full burner during Columbus' lifetime.
The idea that he was born Jewish under halakha borders on the absurd. The idea that he has matrilinear Jewish blood that may or may not qualify as "Jewish" under the laws and/or denomination, not so absurd.