Lower bounds for learning in the membership query and counterexample model Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a minimal DFA of $n$ states is learnable in polynomial time (where the proposed functions are DFAs) with $O(mn^2)$ membership-queries and at most $n−1$ theory-queries ($m$ is the size of the largest counter-example provided by the tutor). Unfortunately, she does not discuss lower bounds.
We can generalize the model slightly by assuming a magical tutor that can check equality between arbitrary functions and provide counterexamples if different. Then we can ask how hard it is to learn classes bigger than regular languages. I am interested in this generalization and the original restriction to regular languages.
Are there any known lower bounds on the number of queries in the membership and counterexample model?
I am interested in lower bounds on the number of membership queries, theory queries, or trade-offs between the two. I am interested in lower-bounds for any class of functions, even for more complicated classes than regular languages.
If there are no lower-bounds: Are there known bariers to proving query lower bounds in this model?

Related questions
Are there improvements on Dana Angluin's algorithm for learning regular sets
Yes, some lower bounds are known. For example, assuming $NP \neq coNP$, you cannot even properly learn read-thrice DNF formulas in polynomial time.  There is a whole paper developing such hardness results using something called the "representation problem".

To answer your linked-to question: Schapire, in his dissertation, in addition to proving that "weak learning" = "strong learning," also improved on Angluin's bound and gave an algorithm that uses $O(n)$ equivalence queries and $O(n^2+ n \log m)$ membership queries for learning DFA.

One easy way to get lower bounds is information-theory.  You can figure out how many distinct targets there are and how many bits a query gives you, etc.  These upper bounds come close but aren't there.  There are also issues one needs to think about regarding how the "counterexamples" arrive to the learner.  A well-chosen counterexample can give away quite a lot of information.

Update to the discussion above: Angluin and Dohrn address the question learning with random counterexamples in a recent paper.