Since there are still languages spoken by people that did until recently not practice agriculture or eat soft foods, such as the aboriginals of Australia and the bushmen of the Kalahari, would it not be possible to test this hypothesis and see if they use labiodentals in their speech?

Is being born with an underbite a throw back to how our jaws were before we chewed softer foods?

The inability to make certain sounds would not at all interfere with the development (or utility) of language, only the form the language would take. Even today, when we all have more or less the same jaw structure, there are sounds that may exist in one language that are incomprehensible or unpronounceable in another. "Spoken" language does not even require sounds at all, eg., ASL

Agriculture is only about 10,000 years old. Is this enough time for evolution to make a major change such as this? Maybe the discovery of fire for cooking, a technique much older than agriculture and which also has the effect making food easier to masticate, was of greater influence.

I interesting

When I was getting my degree in archaeology, I took a classes in environmental anthropology and in paleoanthropology. We learned that as environments changed adaptations occurred with along with the changes. Its not so deterministic as natural selection. As a new food source made its way into the diet of populations, those best suited to masticating the new entrants had a selective advantage over those that did not. Also, the ability to breakdown and digest the cellulose and fiberous plant material in the new plant foods had an advantage. Therefore, both mastication and digestion evolved hand in hand with dentition and jaw adaptation. Those that were able to acquire both were again at a selective advantage.

Language changes were a secondary advancement adjoining the change in jaw and dental changes. One of the key evolutionary developments that humans developed was a complex communications structure (aka. Language). Early survival depended upon complex vocalizations and communications. Early humans were much smaller than their prey and their predators. It took a greater complexity to communicate cooperative tasks, thus society developed. Therefore, it is no so much deterministic, rather just a good case for natural selection over many generations, not overnight.