Interesting topic. I did not see the program. From the History Channel website the program looks to be Hardcore History: Ancient Monster Hunters.
Mayor's theory seems plausible, even obvious. I'm not sure why some scientists are miffed by it. Maybe it's a case of why-didn't-I-think-of-that causing professional jealousy, or perhaps it's that Mayor is not a "professional" scientist. I googled her and the only reference to her training I could find said that she's a folklorist with a BA in Folklore and Classical Studies from the Univ. of Minnesota, 1976.
I was curious as to what Aristotle thought about fossils. Googling again (ain't the internet great), Aristotle believed that the Earth and all its lifeforms were eternal and unchanging, therefore fossils could not be the remains of ancient, extinct species. His theory was that fossils were formed in situ by a mysterious inorganic process. From what I gather, he thought they were geological formations that never were living beings.
So the ancients did know of and give serious thought to the existence of fossils. As they attempted to integrate fossils into their limited understanding of the natural world, they came to some, ummm, interesting conclusions. And then, as Pausanias noted (from your http://homepage.mac.com/cparada/GML/BESTIARY.html link), "Those who like to listen to the miraculous are themselves apt to add to the marvel, and so they ruin truth by mixing it with falsehood." Thus we have the myths of griffins, giant humans, etc. Seems entirely plausible.
For anyone interested, here are some http://hometown.aol.com/afmayor/myhomepage/index.html .