Tenure-track reference letters: previous supervisors versus outsiders I remember reading in The Professor Is In that the tenure-track references should be from external members, not only your past advisors/supervisors. 

That book is written aimed at social sciences, maybe, so, for Computer Science, in Canada (and the US), how important is it really? 

I imagine that it would not be a dealbreaker for a rockstar, and that exactly how much impact would depend on the case/institution/competition, but what can I expect the impact to be?
It's a lot harder to have non-advisors write letters for a tenure-track application in most STEM fields, largely because of the more direct connection between projects, funding, and supervision in STEM fields versus humanities fields.

In the applications I've reviewed as a hiring committee member in engineering, pretty much every letter came from either a PI or co-PI of a project the applicant worked on as either a graduate student or a postdoc. If there was a letter from an "external" member, I don't recall seeing it. However, it certainly wouldn't hurt if such letters were available, so long as it's a helpful letter of recommendation.