Tarek Hefni, a Cairo college student, response to Obama’s speech:

“I did not feel very comfortable regarding the two state solution and regarding treating the Holocaust as a fact. It is still a debatable issue and should not be taken as granted….I also don’t see any relevance between people being killed by other nation and building a homeland in a different land.”

In other words, a genocide doesn’t make a case for Israel’s right to exist.
Ironically, the Jewish Anti-Defamation League made a similar point:

“While he made strong statements against anti-Semitism and Holocaust denial, it should have been made clear that Israel’s right to statehood is not a result of anti-Semitism and the Holocaust. “

Similarly, both sides objected to an implied equivalence between the treatment of Jews and the treatment of Palestinians — with Palestinians objecting that it minimized the suffering of Palestinians and Jews saying it minimized the suffering of Jews.
On the first point, I actually would argue that the Holocaust, and historical persecution in general, is the most universally persuasive argument for Israel’s right to existence. If you base it on Biblical justifications, then Palestinians can argue that at various other points in history they were the primary population in the land. The Holocaust added a new fact to the discussion — the reality that anti-semiticism is so virulent and pervasive that only a separate state could possibly protect Jews.
But i find it fascinating that it’s an argument that seems to be unpersuasive to many Jews, and depressing that it’s unpersuasive to Arabs.
On the second point, the idea that Obama dissed one or the other of them by equating Pallestinian suffering with the Holocaust, I have to admit, I didn’t hear the speech that way. Yes, he followed the Holocaust passage with the phrase, “on the other hand,” and then discussed Palestinian suffering — and I definitely can see how both sides would view an implied equivalence.
But read again that controversial sentence: “On the other hand, it is also undeniable that the Palestinian people – Muslims and Christians – have suffered in pursuit of a homeland.” He did not say “suffered equally” or “suffered just as much.” He just said they suffered, too, and that that’s a very important factor. I’m not sure I agree that saying both historical realities are crucial to the discussion means that they were equally egregious problems.
I also believe that any risk to that formulation was greatly out-weighed by the crucial importance of Obama standing in Cairo, telling the Arab world that it is a “fact” that six million Jews died. For many young Arabs, Obama may be the most credible person they’ve ever heard say that.