With the clock ticking on a 72-hour deadline for Al Qaeda (search) militants to be freed or else an American hostage will die, the U.S. State Department said it was doing everything it could to save Paul Johnson short of negotiating with the terrorists.
An Islamic Web site broadcast video Tuesday from Saudi Arabia that showed Johnson blindfolded and sitting in a chair with his profile to the camera, a large tattoo on his left arm. It displayed his Lockheed Martin (search) identification card.
State Department spokesman Richard Boucher (search) said Wednesday "our hearts go out to Mr. Johnson and his family," urging the "people of the world" to unite against individuals and groups who use terrorist tactics to pursue political goals.
"The U.S. government will use every appropriate resource to gain Mr. Johnson's safe release and return to his family and home," he said. However, it is also U.S. policy not to negotiate with hostage-takers.
Boucher said the U.S. has people on the ground in Saudi Arabia that have "been in close touch with their Saudi counterparts on this matter," and will provide the Saudis with "any assistance they need or request."
During an interview with Fox News' Rita Cosby, Jordan's King Abdullah (search) spoke strongly about those behind the kidnapping, saying "these people are the devil." He added, "How they can use any religion or the name of God to capture, hurt, kill innocent civilians in the name of God for me is shocking."
He also added that despite the images being shown, "It is impossible to negotiate with terrorists."
Adel al-Jubeir, foreign affairs adviser to the Saudi government, said shortly after the video appeared that the kingdom would consult with the Bush administration about how to proceed, but Riyadh like Washington has a strict no-negotiation policy.
Al-Jubeir also said the current situation with the Islamic militants was not a crisis but a serious issue that the Saudi kingdom will be dealing with for some time.
"Their strategy is to try to sow fear in people's hearts, and to panic, and to cause an exodus of foreign workers from Saudi Arabia, in particular Westerners," he said.
"They are trying to scare foreign workers into leaving Saudi Arabia because they believe it will weaken the Saudi economy and consequently weaken the Saudi government, but they are mistaken."
'I Am an American'
"My name is Paul Marshall Johnson, Jr.," the seated hostage says in the tape. "I am an American. ... I work on Apache helicopters."
Johnson, 49, of Stafford Township, N.J., worked for Lockheed Martin in Saudi Arabia.
He was seized Saturday by a group calling itself Al Qaeda in the Arabian Peninsula. The organization is believed to be headed by Al Qaeda's chief in the kingdom, Abdullah-aziz al-Moqrin.
The tape on the Web site, http://www.hostinganime.com/sout18/, showed a hooded man read a statement and holding an AK-47 rifle. As the man was reading, a subtitle on the screen identified him as al-Moqrin.
His statement was similar to a printed message on the Web site that carried the name of Al Qaeda in the Arabian Peninsula. It said the group gave Saudi authorities 72 hours to release "mujahadeen" militants or it would kill the hostage.
A U.S. official said the threat should be taken "very seriously" because the posting appears to be credible and militants have used the site before. "It has been a good indicator in the past," the official said, speaking on the condition of anonymity.
The statement on the Web site says the holy warriors of the Arabian peninsula's Fallujah Brigade has "hit" the engineering team that "oversees the development of the American Apache helicopter that attacks Muslims in Palestine and Afghanistan."
It says: "The Fallujah Brigade has killed the director of this team and kidnapped one of its engineers, Paul Johnson, and if the tyrannical Saudi government wants their American master to be released, then they have to release our holy warriors that are held in Ha'ir, Ruweis and Alisha prisons within 72 hours of this statement's date."
The day Johnson was abducted, Islamic militants shot dead another American, Kenneth Scroggs, from Laconia, N.H., in his garage. Scroggs was the third Westerner killed in a week, after the shooting death of an Irish cameraman for the British Broadcasting Corp. on June 6 and another American who was killed in his garage June 8.
Saudi security forces arrested a militant north of Riyadh on Tuesday as they stepped up their presence in and around the city in a hunt for Johnson's kidnappers.
Westerners Moving to High-Security Compounds
Also Tuesday, Saudi Arabia's ruling crown prince warned Islamic militants that the kingdom planned shortly to deploy more security forces than they had ever faced before.
"Be assured that the kingdom has enough men whom you haven't seen so far, but within the coming few days you will see them," Crown Prince Abdullah told the militants, whose attacks have increased during the past three months. His remarks were televised.
Westerners in Saudi Arabia are responding to the attacks by moving to high-security compounds or even to Bahrain, and by pushing for the right to armed private guards, according to diplomats and real estate agents.
Western embassies in Riyadh, the Saudi capital, are negotiating with the government for a relaxation of the ban on private security guards carrying firearms, a Western diplomat said, speaking on condition of anonymity.
Fox News' Teri Schultz, Rita Cosby and the Associated Press contributed to this report.