The complexity of sampling (approximately) the Fourier transform of a Boolean function
The Kushilevitz-Mansour algorithm in learning theory establishes, that whenever $\hat{f}(x)$ is approximately sparse, i.e. there are only $O(poly(n))$-many large Fourier coefficients of absolute value $\Omega(1/poly(n))$, then we can find their locations and approximate their complex values in $\sf{BPP}$. Of course you can also efficiently sample from that list. To be precise, Kushilevitz-Mansour only talked about Fourier transforms over $\mathbb{Z}_2$, but generalization to FTs over general finite Abelian groups (see e.g. Akavia's thesis) are known.

As an application of this to quantum computing, one can show that the output state of quantum circuits structured in blocks of Hadamard-Toffoli-Hadamard gates can be efficiently approximated given the promise that the output state written in the computational basis is approximately sparse (see my QIP'2010 poster here, and the pre-print here). If the sparsity assumption is dropped, we could simulate Simon's algorithm (or Shor's), which is of exactly that structure, contradicting the $\Omega(2^{n/2})$ query lower-bound for Simon's problem.