Fuzzers have evolved over the years, keeping pace with protocol complexity. As in any evolution, it has not been a steady process, but one of peaks, advancements, and even regressions. Within the last year, Spike has become one of the best fuzzers. The main reason for this is that Spike took the block-based approach that many other fuzzers were lacking. Most researchers agree that while the block-based approach takes more time to start, the results provided are usually quite worth it, especially when you consider the same script can be used to fuzz multiple applications.
When looking for the next generation of fuzzers, look for these features:
Less time required for adding new protocols or file types
Integration of a debugger/monitoring with the fuzzer itself
Written in a portable language (Perl, Python, Ruby)
Ability to connect to different types of outputs (TCP, UDP, file, named pipe, com)
Weighting attack vectors
One new fuzzer claiming to meet most of these requirements is Autodafé (http://autodafe.sourceforge.net). At the time of this writing, it has the ability to create basic block-based scripts from packet capture, integrate the debugger with the fuzzer, and trace bad function calls (if a fuzz vector does not affect any of these, it is just skipped to improve fuzz time).
The approach taken by Autodafé is more grey box that pure black box, since the fuzzer and the debugger work together. Autodafé also works for file-based fuzzing and allows the support of multiple protocols. Since it is able to partially process and recover information from network dumps (almost automatically), adding a new protocol to Autodafé is easy.
Assuming Autodafé continues to mature, it is surely worth the effort to check it out.