It was not immediately clear why Khaled Al-Qazzaz, a father of four, had yet to be freed.
In an interview, his wife said the family's jubilation at the release order has given way to worry at his ongoing detention.
"Our initial reaction last week was happiness and excitement," Sarah Attia told The Canadian Press.
"We're getting a little nervous because it's taking so long but we're trying to remain positive and hopeful that this will end in a few days."
Al-Qazzaz, 35, a University of Toronto engineering graduate, is a former aide to ousted president Mohammed Morsi. He was arrested along with Morsi and eight other aides in July 2013 when the Egyptian military removed the president from office. Egyptian authorities never charged him nor explained why they arrested him.
The case has attracted attention from human rights activists and groups, such as Amnesty International.
Attia, 34, said the attorney general's release order issued Monday last week has been communicated to Al-Qazzaz and his lawyers and should have taken only two or three days to be executed.
"It's hard to tell at this point what is holding it back," she said from her home in Toronto. "We don't know if it's just technicalities or if there's another reason."
Al-Qazzaz is said to be suffering from a severe spinal condition related to his detention and is in need of surgery. The hope, Attia said, is that he will be able to fly back to Canada as soon as he's free so he can undergo needed surgery.
He was transferred to hospital in Cairo from solitary confinement two months ago — after apparently losing motion in his arms and suffering severe pain. The Toronto-born Attia said she had not had a chance to talk directly to him but his family in Egypt has.
The couple, who met when she was also studying engineering at the University of Toronto, went to Egypt in 2005 to open a school before getting caught up in the turmoil that saw Al-Qazzaz arrested at the president's office.
The couple's boy and three girls, aged 2 to 8, are excited at the prospect of seeing their father again, even though the youngest would not recognize him, their mom said.
"I try to keep them hopeful, still," she said.
"He needs to come here to be with us ... and to put his life back together."
In a separate case, an Egyptian court on New Year's Day ordered a new trial for Canadian-Egyptian Mohammed Fahmy and two other Al-Jazeera journalists.
The trio was arrested in Cairo in December 2013 and accused of spreading rumours harmful to national security. They were convicted last June — the judge said they were brought together by the devil to destabilize the country — and Fahmy was sentenced to seven years.
Foreign Affairs Minister John Baird, who has previously raised Al-Qazzaz's case with the current Egyptian regime, was slated to fly to Cairo this month.