What is the complexity of distinguishing a true Fourier spectra from a fake one?
Sorry I'm late -- it's a wonderful question!  As others have already pointed out, that's exactly why I asked the question in my BQP vs. PH paper, and why I spent 4 or 5 months working on it without success back in 2008.  One way to answer the question would have been to prove a much more general statement that I called the "Generalized Linial-Nisan Conjecture"---but unfortunately, that conjecture turned out to be false, at least for circuits of depth 3 and higher.  (I still think it's probably true for depth-2 circuits, which would at least yield an oracle separation between BQP and AM.)  For more recent ideas (the latest, as far as I know) toward an oracle separation between BQP and PH, see the nice followup paper by Fefferman, Shaltiel, Umans, and Viola.