Considering some of the others who have received the Order, I see no reason why Klein does not qualify. I am not a Klein supporter BTW. When in power he was actually bad for Alberta, frequently using sarcasm and insults to stifle debate and actually putting together a Nixon-style "enemies" list of people and organizations he had to get.
His term in power featured incredible luck, taking office when oil prices were low and within a few years seeing increases that resulted in huge government surpluses. At the same time he privatized many government services resulting in increased costs for the average Albertan without any real improvement in service. He also allowed Alberta's infrastructure to decline, particularly in the critical areas of health care, education, and transport. None of his so-called "reforms" actually resulted in any real savings for the government (health care costs actually soared during the years when Klein served as Premier), and many changes actually created long term problems that still have not been remedied. Essentially Klein was a one-trick-pony focused on eliminating the provincial debt at any cost and without any real vision for the future.
However, having stated all of this, I see no reason why an award that has been handed out to professional athletes and entertainers should not be handed out to a professional politician.