According to NFL.com's Freakonomics series, no.
In their book Scorecasting, Tobias J. Moskowitz and L. Jon Wertheim marshal the most compelling evidence to date on the subject, analyzing "pressure" kicks from 2001 through 2009 while controlling for distance of the field-goal attempt. They found that icing the kicker certainly doesn't produce the desired effect, and in some cases might even backfire. The one situation in which icing might confer a slim advantage: When there are fewer than 15 seconds left in the game. Here's their data:
Field goal success whether opponent calls a timeout or not
(Percentage of kicks made)
Situation All kicks Iced Not iced
Less than 2 min. left in fourth quarter or OT 76.2% 74.2% 77.6%
Less than 1 min. left in fourth quarter or OT 75.5% 74.3% 76.4%
Less than 30 sec. left in fourth quarter or OT 76.5% 76.0% 76.9%
Less than 15 sec. left in fourth quarter or OT 76.4% 77.5% 75.4%
A recent Grantland article suggests that the only reason coaches still try icing is that from their standpoint, it's low-risk and high-reward. Everybody "knows" icing the kicker is what to do, so if they try and fail, it's no big deal, while if they try and succeed, they're "geniuses" – even though the data points more towards luck.
The NFL has banned calling two or more consecutive timeouts; I don't know if that would be more effective or not, but it would certainly be annoying to fans.