CAIRO, Egypt – President Barack Obama chose an Arabic satellite TV network for his first formal television interview as president, part of a concerted effort to repair relations with the Muslim world that were damaged under the previous administration.

Obama cited his Muslim background and relatives, practically a taboo issue during the U.S. presidential campaign, and said in the interview, which aired Tuesday, that one of his main tasks was to communicate to Muslims "that the Americans are not your enemy."

The interview on the Dubai-based Al-Arabiya news channel aired as Obama's new envoy to the region, former Sen. George J. Mitchell, arrived in Egypt on Tuesday for a visit that will also take him to Israel, the West Bank, Jordan, Turkey and Saudi Arabia.

Obama said the U.S. had made mistakes in the past but "that the same respect and partnership that America had with the Muslim world as recently as 20 or 30 years ago, there's no reason why we can't restore that."

Obama also emphasized the importance of engaging with Iran, a country the Bush administration often singled out as the most dangerous in the region.

Obama condemned Iran's threats against Israel, pursuit of nuclear weapons and support of terrorist organizations, but said "it is important for us to be willing to talk to Iran, to express very clearly where our differences are, but where there are potential avenues for progress."

Obama's predecessor, former President George W. Bush, launched wars in Iraq and Afghanistan which prompted a massive backlash against the U.S. in the Muslim world.

In contrast to the enthusiastic reception Obama's victory has garnered around the world, the Arab world has been much more cautious about the new U.S. president — with most people skeptical that American policy in the region will change substantially.

"I can't be optimistic until I see something tangible," said Hatem al-Kurdi, 35, a Gaza City engineer who saw parts of the interview. "Anyone can say nice words, but you have to follow with actions."

"He seems very interested in the Middle East issue but he didn't say exactly what he's going to do about it," Kurdi added.

After earlier dismissing Obama as following the same policies as his predecessor, officials from the militant Palestinian Hamas group softened their stance against the new president Tuesday.

"In the last couple of days there have been a lot of statements (from Obama), some of them very positive, and choosing this George Mitchell as an envoy," said Ahmed Youssef, a senior Hamas official interviewed on the Doha-based Al-Jazeera news network. "I think there are some positive things we have to count."

Obama's choice of Al-Arabiya network, which is owned by a Saudi businessman, follows the lead of the Bush administration, which gave several presidential interviews to that news channel.

"The U.S. sees Al-Arabiya as a friendly Arab channel, whereas they see Al-Jazeera as confrontational," said Lawrence Pintak, director of the journalism training center at the American University in Cairo.

Hady Amr, director of the Brookings Doha Center, an arm of the U.S. think-tank in the Qatari capital, described decision to make the first presidential interview with an Arabic news network as "stunning."

"President Obama has made it absolutely clear ... that a central priority will be repairing America's relations with the Muslim world," he said. "If that's his objective, I'd say he's been hitting home run after home run."

In the interview, Obama called for a new partnership with the Muslim world "based on mutual respect and mutual interest." He talked about growing up in Indonesia, the Muslim world's most populous nation, and noted that he has Muslim relatives.

Obama's Kenyan father was born Muslim, though a self-described atheist, and many of his relatives in Kenya are practicing Muslims. As a child, Obama lived for a number of years in Indonesia while his mother as doing research there.

This appeal does seem to have struck a chord among many Muslims.

"He's different from the previous presidents, perhaps because of his color or his Islamic background. My views of America are different now than they were during the Bush administration," said Youssef Ali, 45, who works for the Iraqi Electricity Ministry in Baghdad.

Most of Obama's interview focused on the Israeli-Palestinian conflict, which is widely perceived in the Middle East as the most pressing issue in a region filled with animosities.

Obama said he felt it was important to "get engaged right away" in the Middle East and had directed Mitchell to talk to "all the major parties involved." His administration would craft an approach after that, he said.

"What I told him is start by listening, because all too often the United States starts by dictating," Obama told the interviewer.

The president reiterated the U.S. commitment to Israel as an ally and to its right to defend itself. But he suggested that both Israel and the Palestinians have hard choices to make.

"I do believe that the moment is ripe for both sides to realize that the path that they are on is one that is not going to result in prosperity and security for their people," he said, calling for a Palestinian state that is contiguous with internal freedom of movement and can trade with neighboring countries.

On Tuesday, Gaza's fragile truce was threatened when a bomb detonated by Palestinian militants exploded next to an Israeli army patrol along the border with Gaza, killing one soldier and wounding three.

Obama also said that recent statements and messages issued by the al-Qaida terror network suggest they do not know how to deal with his new approach.

"They seem nervous," he told the interviewer. "What that tells me is that their ideas are bankrupt."

In his latest message on Jan. 14, al-Qaida leader Osama bin Laden said Obama had been left with a "heavy inheritance" of Bush's wars. Shortly after the election, the network's number two, Ayman al-Zawahri described Obama with a demeaning racial term for a black American who does the bidding of whites.

The message suggested the terror network was worried Obama could undermine its rallying cry that the U.S. is an enemy oppressor.

"There's no actions that they've taken that say a child in the Muslim world is getting a better education because of them, or has better health care because of them," said Obama about al-Qaida.

_____

Associated Press Writer Adam Schreck contributed to this report from Dubai.