General
AllTheWeb's news search is quite new but very good. It includes over 3,000 news sources, which it indexes constantly, making it very fresh. Each results says how long ago it was indexed (hours, not days). Fast Search claims to index up to 800 articles per minute.
Search Help
AllTheWeb's news search is very similar to its web search, using the same search syntax, and many of the same options.