Alan Johnston was abducted near his Gaza home on March 12, sending shockwaves through the Palestinian public and media, who have since pressed the government to secure his release.
Johnston, who appeared calm and healthy in the video, called for the lifting of international sanctions against the Palestinian government, and condemned the U.S. and Britain's actions in Iraq.
The footage appeared on the Al-Ekhlaas Web site, with the logo of the Army of Islam, a militant Palestinian group believed to be holding the reporter.
The Army of Islam released a 20-minute video previously, showing Johnston's press card and demanding the release of a radical Islamist held in a British jail.
His abductors set three preliminary conditions for his release in early May, the Palestinian newspaper al-Quds said Monday citing well-informed sources.
They demanded that the Palestinian authorities provide them with a plot of land, release an Iraqi terrorist from a Jordanian prison, and pay a $5 million ransom.
The paper said negotiations with the kidnappers were proceeding with difficulty, and that the reporter was unlikely to be released any time soon.
In mid-April, hundreds of Palestinian reporters stormed the Gaza legislature in protest at the government's failure to secure Johnston's release after leaflets claiming he had been executed were discovered.
PNA officials, who unsuccessfully tried to negotiate Johnston's release March 13, vowed to do what they could to get the U.K. reporter back.
Johnston had been working in Gaza on a permanent basis for the past three years, and is now one of a handful of foreign journalists and aid workers abducted in the Palestinian enclave in the past two years.
On April 12, U.N. Secretary-General Ban Ki-moon also called for Johnston's immediate release.
In all previous cases, the victims were released unharmed after a few days.
