I don't think political patronage is the answer, since of 11 members of the council that recommends appointments, only 2 were appointed to the positions that make them members of the council by a Liberal PM (Beverley McLachlin and from everything I know about the Canada Council for the arts, Karen Kain). There are an equal number of posts appointed by the current government.
I think it would be inappropriate to judge appointments to the Order based on the personal politics of the person. As much as others may dislike him, Jean Chretien did serve in politics for 40 years, during 10 of which he was the Prime Minister.
The Constitution of the Order of Canada The Constitution of the Order of Canada:
Appointments of persons as Companions and honorary Companions shall be made in recognition of their outstanding achievement and merit of the highest degree
Being elected Prime Minister for 3 terms (though admittedly with a weak opposition) is an outstanding achievement. Hopefully one day Stephen Harper will be able to join Chretien, Mulroney, Clark, and Turner as a Companion of the Order