Could people of Classical antiquity ever encounter the art of prehistoric cultures? If they did, could they possibly recognize it as such?

The Mycenaean civilization, which flourished in Greece during the late Bronze Age (1600-1050BCE), left behind some very conspicuous pieces of monumental architecture that the people of classical antiquity not only encountered, but interacted with and incorporated into their own understanding of the development of their own civilization.

Large sections of Mycenaean citadels such as Mycenae and Tiryns were built with huge, roughly interlocking boulders. This style of stonework is known as "Cyclopean" masonry by modern archaeologists based on the ancient Greek belief that only the giant Cyclopes could have moved such massive rocks and put them into place. Its easy to see how this explanation seemed believable. I mean look at the size of the lintel above the Lion Gate at Mycenae!

Pliny the Elder, a Roman natural philosopher who lived in the 1st century AD, writes about the development of the arts in the 7th book of his Natural History. He offers the following accounts of the origin of architecture:

Wells were invented by Danaus, who came from Egypt into that part of Greece which had been previously known as Argos Dipsion. The first stone-quarries were opened by Cadmus at Thebes, or else, according to Theophrastus, in Phœnicia. Walls were first built by Thrason; according to Aristotle, towers were first erected by the Cyclopes, but according to Theophrastus, by the Tirynthii. - Pliny, Natural History, 7.57

So, regarding the second part of your question, to some extent, yes. One of Pliny's explanations is that the "Tirynthii" (ie. Myceneans) were the first to build "towers". Another way in which the people of classical antiquity explained prehistoric architecture that is evident in this passage is myth (ie. The Cyclopes). But even this explanation at least dates the ruins to the distant past.

The mythological understanding of the Mycenaean ruins is echoed by Pausanias, a Greek traveler and geographer from the 2nd century AD:

Going on from here and turning to the right, you come to the ruins of Tiryns. The Tirynthians also were removed by the Argives, who wished to make Argos more powerful by adding to the population. The hero Tiryns, from whom the city derived its name, is said to have been a son of Argus, a son of Zeus. The wall, which is the only part of the ruins still remaining, is a work of the Cyclopes made of unwrought stones, each stone being so big that a pair of mules could not move the smallest from its place to the slightest degree. Long ago small stones were so inserted that each of them binds the large blocks firmly together. - Pausanias, Description of Greece 2.25.8

By the way, Pausanias' Description of Greece is a MUST read if you are interested in how the ancient world and its monuments were perceived by a relative contemporary. It's basically the ancient equivalent of a travel blog. A lot of the sites he describes were already centuries old by the time he wrote but were still functional and well-maintained. He is a great source to compare fragmented art and architecture against because his descriptions help fill in the "missing pieces".