There was something wrong with that picture. Of course all the best politicians are skilled actors, so they did their best to hide the reality. But, despite the smiles and the handshake, Barack Obama, Mahmoud Abbas and Binyamin Netanyahu could not quite conceal the weirdness at the centre of their photo-op in New York today. What the image should have conveyed was the gratitude of the leaders of two minor states, happy to be basking in the sunlight radiated by the global emperor. Instead they looked sullen and reluctant, as if they had done Obama, leader of the world's sole superpower, a favour by turning up.

How had it come about that, in the words of the Israeli columnist Nahum Barnea, the Americans had "discovered that they want an Israeli-Palestinian peace agreement more than the Israelis and the Palestinians want it"? The narrow answer is the usual one, that the local politics on both sides of the conflict has made inaction a safer bet than action. Netanyahu sits atop a coalition that is perfectly stable – just so long as he doesn't do anything. Were he so much as to hint at taking any of the steps necessary for a peace deal, coalition partners would start breaking off like aeroplane wings in an ice storm. As for Abbas, he has finally acquired some political strength, removing potential rivals from within his own Fatah faction while all trace of Hamas has been eradicated from the West Bank. As one Fatah insider puts it: "Abbas is now at the peak of his powers." All that could damage him are the accusations of treachery that would instantly follow any compromise with Israel.

So Netanyahu and Abbas had something in common: neither wanted to meet the other. Abbas didn't want to break his earlier pledge that he would only start talking if Israel agreed to a complete freeze on settlement building. And Netanyahu refused to agree to any such freeze. In the end they came to the Waldorf only because Obama deployed the one weapon no Israeli or Palestinian leader can resist: a direct invitation from the American president.

The gloomy conclusion to draw from this diplomatic dance – a routine whose key step has been footdragging – is that Barack Obama is a diminished figure in the Middle East, and perhaps around the world. Having been inaugurated after a landslide victory that gave him the heftiest stock of political capital in a generation, Obama no longer seems to command the fear, or even the respect, that is a basic tool of the job. Scan the Arab or Israeli press of recent days and you see commentators queueing up to brand Obama as a weak naif who got suckered. On the Arab side, he demanded a few gestures of normalisation towards Israel – overflight rights for El Al jets and looser rules on tourist visas, for example – from the so-called moderate states and got next to nothing. Humiliation came in June when he went to Saudi Arabia only for the king to say no to his face.

With the Israelis he fared no better. He issued a demand that could not be nuanced or fudged: he wanted a total halt to settlement construction. No ifs or buts. Bibi has revelled in his refusal, the Israeli public and press applauding as he shows the US president the finger. Barnea called the New York meeting a "joke at the expense of Barack Obama, who took one look at Middle East politics and got burned".

Even Obama's friends worry that he has lost face in a region where face matters, his authority further weakened by the sight of him struggling to get his way on domestic policy at home. Veterans of the peace process on both sides agree that the key mistake was the demand to freeze settlements. Every US administration has called for a halt – some more sincerely than others – and none have ever got their way. Obama might have proved the exception had he been prepared to escalate his standoff with Bibi, to increase the pressure once Israel's first answer was no. But he was not.

Menachem Klein, a scholar and adviser to the Israeli delegation during the Camp David peace talks of 2000, reckons the settlements gambit might have worked had it been framed differently. Obama could have called not for a freeze of all settlements – including those regarded by many Israelis as glorified suburbs of Jerusalem – but for the dismantling of the more egregious ones, those far-flung towns and villages that no one believes will remain under Israeli sovereignty in a plausible peace deal. Next, Obama could have offered a quid pro quo, centred on assurances on security. That way, says Klein, Obama would have overcome the resistance of those Israelis "who have been asking why they should give up something for nothing". The president would have separated the Israeli mainstream from the ideological hardcore of settlers. Instead they have been united – behind Netanyahu.

Plenty of Obama critics have seized upon this first setback as evidence that the president is in over his head on foreign policy. A failing strategy in Afghanistan, rejection of his outstretched hand to Iran, "capitulation" on missile defence to Russia – all make it on to the anti-Obama charge sheet.

It makes a neat thesis but it is, at the very least, premature. Obama's achievement yesterday was modest, but it was not nothing. In the end, both Netanyahu and Abbas had to bend to his will. They heard him insist that Middle East peace is a national security interest of the US, signalling that it will remain a personal priority. By announcing that Hillary Clinton – rather than just his envoy, George Mitchell – will report back to him in mid-October, he has ratcheted up the engagement a notch. He also put the parties on notice that he knows the old games, and will not tolerate them. "We cannot continue the same pattern of tentative steps forward and then stepping back," he said.

It's worth remembering too that Netanyahu has had to budge once already this year, by publicly accepting a Palestinian state – albeit one qualified beyond recognition – and that the ground has now been laid for the next phase. Both sides now have a clear idea of what will be required of them.

Above all, those panicking that Obama has not yet bagged a clutch of foreign policy triumphs in the Middle East and elsewhere may be forgetting both the mess that he inherited and his leadership style. He plays the long, slow game, advancing gradually. So, yes, there was no overnight fix in New York, but that was never on the cards. Besides, Obama believes he has time on his side. Unlike most US presidents keen to play Middle East peacemaker, he has not tackled this in his last year, but in his first.

I'm not sure which view – the ever-shrinking Obama whose credibility is eroding fast, or the careful tortoise who will eventually overtake the hare – is right. It's too early to tell. But either way, Obama needs to shake off that first perception before it congeals. In the Middle East that means pressing the reset button. He could do that with a long overdue direct address to the Israeli people: dispelling the absurd myths that say he is an Arab Muslim congenitally hostile to their country. At the same time, he needs to find a new way to show the Palestinians he can deliver. These are still early days in the presidency of Barack Obama: we must hope that, as with his life story, the first act provides little clue for what comes next.