Answering based on the bounty in 2012. Already some good answers here, but I wanted to make a somewhat different point: the discussion has mostly been about whether users need to the button in order to successfully use the search. But I believe we should also think about what happens before the user takes that action.
How do they find your search? The search button can serve as an indicator. On a busy page or if your search element is non-standard place (ie, not in the top right) the visual scan to find that action may be difficult.
Of course, the importance of having that strong indicator depends on your site's intent, design and audience. Search is vital for Stackoverflow (or UX), but its audience is savvy and the design puts the search in a standard location and it's contrasted well with the background. If your audience is less savvy and/or the search is a critical path for site use, you might want to consider keeping it.
To pick on the super-awesome Stackexchange a bit, I was looking at their English Language site. Here's the search interface:
Easy for me to use, I'm very familiar with their suite of sites. But an older user who comes there looking for grammatical help? A search button could make it more clear. Though I'd argue that make the search background white would be most helpful.