In DNSSEC, NSEC records are used to provide proof of nonexistence. The trouble is that these records provide pointers to existent domain names (the closest known domain in either direction) constructing a chain that can be "walked" to eventually disclose all domain names in a given zone through further failed queries.
The method as I understand it relies on crafting queries for domains that do not have a corresponding record. Are zones with wildcard DNS records still somehow susceptible to this attack?

foo.barsuch thatx.foo.barreturns the same DNS record, for every x ? – curiousguy Jul 4 '12 at 6:31baz.foo.barmay exist, but what aboutqux.baz.foo.bar? – curiousguy Jul 4 '12 at 16:01