This is not as straight-forward as it sounds. Some problems as I see them:
1. Oceanic Exploration Not a New Thing
At the time that Columbus "discovered" the New World, the Vikings had already started and abandoned settlements in North America. Furthermore, many civilizations had already dabbled in oceanic exploration, notably the Chinese.
There is also some evidence that Egyptian vessels may have reached South America, but I digress. What the point here is that human ships had been up and about the ocean for a while before Columbus came along.
Since whales migrate, and this creature would probably follow its prey, what are the chances that no one else before Columbus would have encountered these creatures and not left some kind of record of it? Some survivor floating back to shore, or the horribly mangled corpse of a whale showing clear signs of having been ravaged by a predator. It would spark people's imaginations and stories would be told through the ages.
Of course, you can justify this by having there exist legends of sea monsters, etc.
2. Eating Wood
A large squid, etc may very well attack a boat having mistaken it for a whale. The problem is that once it tries to take a chunk out of said boat it will soon find it rather more difficult than biting a whale. Furthermore, instead of being made of tasty flesh, this new prey is made of ... wood?!
In order for this creature to persist in its attack, it would either have to:
A) Be very, very clever and know that within the wooden hull are tasty humans that it can devour. Or
B) Be incredibly territorial, and not tolerate any "newcomers" to the neighborhood. In other words it attacks the ship not because it is food, but simply because it's there. The problem with this scenario is that any creature which migrates (to follow its prey) doesn't have a set territory, and thus won't be territorial.
There's not a lot of sea creatures which can take on a decent sized ship. Sure, a pod of whales working together can flip a boat, etc, but almost any creature that size does not have a vested interest in doing so - after all, human ships are not only difficult to deal with, they're also quite heavily armed.
Remember that exploration and colonization went hand in hand with slavery and conquest, so these explorers were typically very well armed. In fact, those first explorers to reach the New World have been remembered not as peaceful discoverers, but as Conquistadors, who incidentally slaughtered the indigenous populations and toppled their civilizations. These guys could make short work of a squid or whale attacking the boat - especially since they usually traveled across the ocean in numbers, not in a single boat (not at the that point)
Now to answer your question:
What could take out a boat? As @bowlturner has pointed out, a sufficiently angry whale may do the trick. However, in my opinion, these things would soon find themselves extinct.
Anything massive and vicious enough to take out a ship without survivors eventually either killing it with guns/cannons/harpoons, means that its attack must be both lightning fast, and devastatingly powerful. Especially if it must destroy small fleets of these exploratory vessels as they cross the ocean.
So what would be needed?
In my opinion, something from an age gone by. The Megalodon Shark comes to mind. Scientists disagree slightly as to how big this massive predator was, but most believe it was somewhere around 20 meters (that's over 60 feet) long. This bad boy had a jaw so big, and a bite so powerful that it could rip a smaller whale in half.
I quote from Wikipedia:
Sharks often employ complex hunting strategies to engage large prey animals. Some paleontologists suggest that great white shark hunting strategies may offer clues as to how C. Megalodon hunted its unusually large prey. However, fossil evidence suggests that C. megalodon employed even more effective hunting strategies against large prey than the great white shark ... Fossil remains of some small cetaceans (e.g. cetotheriids) suggest that they were rammed with great force from below before being killed and eaten.
In other words this massive predator would rush from the depths to strike its prey from below with devastating force.
This thing would be clever enough to know that there's advantages to taking out a ship (oh look, yummy treats are jumping in the water!), as well as vicious and smart enough to take on a decent sized vessel in such a way that a harpoon, or gun would not help the crew in the least - it attacks from below, no one can see it coming.
That's my 2 cents, at least.