Bernstein is talking about curve standards. The idea Bernstein is discussing is (his term) curve "rigidity". A rigid curve standard can generate only one or a very few curves. A non-rigid generation procedure might generate millions or billions of different curves. That's bad news, because it means that corrupt standards bodies can search those billions of curves for one with a weakness that only they know about.
The most popular curve standard is NIST's. NIST's curves aren't rigid at all: they start with a random seed. There are as many possible curves you can generate as there are seeds.
Now, we've known for a long time that we want rigid curve generation. The second-most-popular curve standard, the Brainpool curves, attempt rigidity. Bernstein doesn't like the Brainpool curves. BADA55 criticizes Brainpool and other standards for attempting but not fully achieving rigidity. Most rigidity attempts involve starting from some mathematical constant, like the digits or pi or stuff like that. The basic logic of BADA55 is that there are too many constants and variants on constants to meaningfully constrain curve generation. The good guys will say they're starting from pi, and the bad guys will just respond that they're using e, the square root of 2, and sin(2). As long as the bad guys can justify a couple million different combinations of constants, they will have enough search space to find weak curves.
Since Bernstein doesn't know any secret curve vulnerabilities (or isn't publishing them), he models curve vulnerabilities by searching for curves that begin with the bytes B:A:D:A:5:5. If you can make "badass", the logic goes, you can make any evil curve.
The historical context of this paper is worth knowing. There's an ongoing effort to standardize and deploy Curve25519, Bernstein's (very excellent) curve standard. Indeed, it is likely that within a year or two, Curve25519 will be the second-most widely deployed curve on the Internet, because browser vendors appear happy to adopt it (it's fast in software, NIST didn't produce it, and has many good implementations).
But when Curve25519 went to the IETF/IRTF, there was pushback: some people felt the Brainpool curves should be standardized, and Microsoft felt like what should be standardized first should be a "nothing up my sleeves" generation procedure that could produce lots of curves for IETF/IRTF. The debate on the CFRG list was pretty bitter, as was the dialog between Tanja Lange (a Curve25519-associated researcher) and Manfred Lochter (a Brainpool guy) at a recent NIST curve summit.
So the updates in this paper include consideration of the Microsoft NUMS procedure, in addition to Brainpool and ANSSI.