Schneier's reasoning is basically this: we don't know what cryptanalysis the NSA is capable of (Schneier might after seeing the leaked documents, but he's not letting on). But it is likely that if there were a weakness it would likely affect only certain categories of curves. The random curves were (presumably) chosen at random, but so were the Koblitz curves: there are many possible Koblitz curves, and the specific ones enumerated in the standard (like secp256k1) were purportedly chosen at random from the set of possible Koblitz curves of that length. But here's the rub: how do we know the NSA didn't search through the space of Koblitz curves looking for one that was secure as far as academia knew, but susceptible to attacks based on mathematics only the NSA knew?

Pre-Snowden, this would have been considered tinfoil hat paranoia because it is not a new concern. The exact same situation existed with DES, which was the federal standard for cryptography for decades. Designed by IBM but with parameters chosen by the NSA, some paranoids thought they had inserted a back door (there was even a Senate investigation). But as we later found out, the tweaked S-boxes strengthened the algorithm against differential cryptanalytic attacks, which weren't known to the public until recently.

The rules of the game until now had been: we work with the NSA through NIST competitions to standardize cryptography. The NSA continues to collect the intelligence it needs through exploiting side channels, weak random number generators, bugs, and even strong-arm techniques, but the algorithms are secure. You can trust the math.

These new revelations apparently throw that out the window. In recent years the NSA actively pushed NIST for standards that it knew were insecure. Not easy-to-get-wrong, like DSA (choose a predictable K value, or reuse an old value and you reveal your private key - a slight of hand that puts the master keys inside the RNG, something which the app has little control over and the NSA can influence), but rather fundamentally broken in subtle ways. How do we know they did not do the same for ECDSA, or any other standardized crypto system that has chosen parameters?

Schneier is justified in his recommendation, IMHO. But there is one bright spot: even if the standard ECDSA curves were broken in this way, if you do not reuse addresses it would not concern you as no public key or ciphertext is available until the coins are spent. So don't re-use bitcoin addresses (you shouldn't anyway).

EDIT: gmaxwell, was the algorithm for parameter selection published? If so, I must have missed this.