How does the BosonSampling paper avoid easy classes of complex matrices?
Thanks for your question!  There are two answers, depending on whether you're interested in the hardness results for exact or approximate BosonSampling.

In the exact case, we prove that given any n-by-n complex matrix A, you can construct an optical experiment that produces a particular output with probability proportional to |Per(A)|2.  This, in turn, implies that no classical polynomial-time algorithm can sample from exactly the same distribution as the optical experiment (given a description of the experiment as input), unless P#P = BPPNP.  In fact we can strengthen that, to give a single distribution Dn (depending only on the input length n) that can be sampled using an optical experiment of poly(n) size, but that can't be sampled classically in poly(n) time unless P#P = BPPNP.

In the approximate case, the situation is more complicated.  Our main result says that, if there's a classical polynomial-time algorithm that simulates the optical experiment even approximately (in the sense of sampling from a probability distribution over outputs that's 1/poly(n)-close in variation distance), then in BPPNP, you can approximate |Per(A)|2, with high probability over an n-by-n matrix A of i.i.d. Gaussians with mean 0 and variance 1.

We conjecture that the above problem is #P-hard (at the very least, not in BPPNP), and pages 57-82 of our paper are all about the evidence for that conjecture.

Of course, maybe our conjecture is false, and one can actually give a poly-time algorithm to approximate the permanents of i.i.d. Gaussian matrices.  That would be a phenomenal result!  However, the whole point of 85% of the work we did was to base everything on a hardness conjecture that was as clean, simple, and "quantum-free" as possible.  In other words, instead of the assumption

"approximating the permanents of some weird, special matrices that happen to arise in our experiment is #P-hard,"

we show that it suffices to make the assumption

"approximating the permanents of i.i.d. Gaussian matrices is #P-hard."