The first judgment was delivered on 24 August 2008.
Captains John Butera and Dieudonné Rukeba, sentenced to 8 years in prison, after having pleaded guilty, also appealed, according to the radio station.
The representative of the public prosecutor, Captain Ngabo Kayijuka, stated Wednesday before the court presided by General Patrick Nyamvumba that the first judges had erred in law by acquitting the two senior officers, indicated the source without further precision.
The lawyers of both convicts, for their part, criticized the first judgment for not having granted sufficient weight to the guilty plea of their clients and pleaded in favour of a reduced sentenced.
Among the killed clergymen - almost all Hutus - were the archbishop of Kigali, Vincent Nsengiyumva, the bishop of Byumba (Northern Rwanda) Joseph Ruzindana, and the bishop of Kabgayi (central Rwanda) Thaddée Nsengiyumva, then president of the Conference of Catholic Bishops of Rwanda.
At the first instance trial, Ngabo Kayijuka had requested life in prison for the general and the major and 15 years in prison against the two captains.
After a short debate, the trial was deferred until next Wednesday, the defence made the point that it had not yet received the appeal brief of the prosecutor.
The two high ranking officers were tried for complicity to commit murder, the prosecution estimates that the crimes committed by their subordinates constituted a fault of command responsibility.
The four soldiers were, at the time, members of the armed wing of the Rwandan Patriotic Front (RPF, the former rebellion currently in power in Kigali) which put an end to the genocide in July 1994. They had been arrested on 11 June 2008, after, according to the Rwandan army, joint investigations of the Rwandan public prosecutor and the prosecutor at the International Penal Tribunal for Rwanda (ICTR), charged with trying the majority of persons responsible for the genocide.