Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm
The question seems somewhat under-specified in the sense that it did not specify the desired error probability of the procedure. Assuming one means constant error probability, then the above is indeed the best I know. For a detailed discussion see Sec 2.5.2.4 in my book "The Foundations of Cryptography - Volume 1" available at http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html

THE ABOVE IS WRONG. SEE CORRECTED ANSWER BELOW.

Prop 2.5.6 in the aforementioned section proves a much better bound:
The algorithm runs in expected time $O(n \log^3(1/\epsilon))$ 
times the running time of the guessing procedure
(see improvement from $n^2$ to $n$ in the comment right after the proof)
and is correct w.p. $\Omega(\epsilon^2)$. Hence, correctness w.p. $2/3$
is obtained in time (factor) ${\tilde O}(n/\epsilon^2)$, which is optimal in some sense
(see Exer 30).