Let me state at the outset that I liked the speech. It was thoughtful. It was careful. It hit the right notes. It changed the tone. That final point is crucial, because in assessing the reaction to President Barack Obama’s speech last Thursday at Cairo University one can separate out those who liked the speech from those who did not by asking this seemingly tangential question: over the last few years, has tone been an issue in American relations with the Muslim World? Might a change in tone be a useful starting place?

It was not surprising that some observers in the region dismissed the speech out of hand with calls for deeds first, words later. Hamas, in Gaza, and Iraq’s Moqtada al-Sadr both fell into this category, though even they appeared to have been impressed, albeit grudgingly, by the gesture. An array of articles in the American media charted the reactions of ordinary people from Casablanca to Calcutta who were politely dismissive of the President, welcoming his intentions but decrying his lack of policy specifics.

No one expected (or at least no one should have expected) Obama, in a single speech, to solve the Arab-Israeli conflict, remake Iraq or completely alter the poisonous image of the United States that has built up throughout the Muslim World over the last seven years. But if you believe, as I do, that tone matters then it was difficult not to see the Cairo speech as an immensely successful starting point – only a gesture, perhaps, but a gesture heavy with symbolic value. Changing the tone of America’s discourse with the Muslim World had to be the first step in a long of rebuilding trust and influence.

A big part of that change in tone was the President’s acknowledgment that America’s history in the Middle East goes much further back than September 11, 2001 and that, sometimes, it has not reflected well on us. At a Washington DC party Friday night a State Department official grumbled to me about this part of the speech, wondering what purpose was served by reminding people of American failings. I replied that acknowledging the past is important because while most Americans have long forgotten, say, our stage-managed coup against Mossedeq or even our bait-and-switch reaction to the results of the 2006 Palestinian elections, few in the region have done so. Changing what we say is the first step to rebuilding America’s Middle Eastern credibility – but we must follow it up with changes to what we do, and we need to be better about doing what we say.

Obama’s election, his extraordinary personal story, his eloquence and, yes, even his middle name are all potent tools as America begins this rebuilding process. But they are only tools. It is appropriate to demand substance from this president as his policies toward the region evolve. It is equally important to appreciate the gesture he has made, and to acknowledge that rebuilding trust is going to have to be a two way street, and that it is going to take time. What we saw in Cairo Thursday was an excellent start.