Stephen argues that "it is far from clear that terrorists need public support to function" - neither the IRA or ETA had majority support; support from a small group within their communities was enough. And he's right here as well - you don't need majority backing to cause mayhem. But what's important is that justice will shrink that group of supporters, and make it progressively more difficult for a group to function effectively. People do not choose to shelter terrorists or look the other way for no reason, and political ideology alone usually isn't enough to get people to condone or support murder - you need outrage and hatred for that. And those emotions are usually a response to perceived injustice, both historical and personal. Ending the injustice shrinks the pool and starves the terrorists in the long run. This won't eliminate all terrorism, or protect us from isolated loonies like Timothy McVeigh or tight groups like Baader-Meinhof, but it will stop those groups from turning into anything larger.
(I should add that it's the personal injustice that really counts. Nothing drives people to terrorism better than seeing their loved ones killed, maimed, tortured, arbitrarily detained, humiliated, or dispossessed. Look at Palestine. Look at Iraq. Look at the way British torture drove people to support the IRA. If there's one thing we should take from this, it's that any "war on terror" has to respect human rights, otherwise it simply creates recruits and sympathisers for the terrorists.)
Unfortunately, as Stephen points out, there is a problem:
not every grievance can be met in a way that satisfies a community that has embraced terrorism as a strategy. Al Qaeda, for example, does not actually have a set list of grievances, other than the erosion of Muslim power since the middle ages. If all US troops left Saudi Arabia, and all the Jews in Israel left tomorrow, would that disempower AQ? Absolutely not. I think you might have hinted at this when you said "legitimate grievances", but in that case there may be a large class of illegitimate grievances.
Absolutely. Not every grievance is legitimate, and the desire of some Arab terrorist groups to drive Israel into the sea is a classic case in point. That said, we are going to have to find a way of living with those with such grievances in the long term, because they are not simply going to go away. The lack of open religious warfare between Catholic and Protestant in Europe shows that such accommodations can be reached; it's just a matter of getting there.
(Though I have to say that I think Stephen is mistaken about Al Qaeda. It's leaders may be motivated by a desire to restore Muslim glory and what-have-you, but the rank and file, the ones actually conducting the attacks and doing the dying, seem to be motivated by issues such as Iraq, Palestine, and America's support of tyrannical regimes. Justice in these areas would definately disempower them...)
Justice is not the sole solution to terrorism. It must be combined with law-enforcement and possibly military action, but without justice, those solutions will simply fail. If we want to deal with terrorism in the long-term, we need to address its root causes - otherwise we're simply bailing without plugging the hole.