The success with negation-based queries displayed in the example is thoroughly explained in The Structured Search Engine -- http://www.youtube.com/watch?v=5lCSDOuqv1A

TL;DR - Google has added phrase chunking, weights positive/negative words in phrases, and allows negative phrases to modify the search impact of the affected phrases.