One can view Cullen's proposal as reflecting a proportional system for allocating committee seats. But it doesn't mean for a second that any change to Canada's electoral system would come about only based on that structure.
Whatever the committee comes up with will still have to be dealt with through legislation in a Parliament in which the Libs have a majority. And that means what Cullen has suggested would in fact serve to confirm the legitimacy of any new system under all plausible interpretations of the results generated by the current one.
By way of explanation, it's fairly clear that the range of options under serious consideration includes three primary types of electoral system. Two of them - first-past-the-post (to the extent it's seen as an option in light of the Libs' promise to scrap it) and ranked ballot - would both have resulted in Lib majorities based on 2015 voting patterns. (Of course, we don't have direct information about what voters' alternative preferences would have been in 2015. But if one ignores the simulated results prepared based on alternative data, that's not a problem capable of being remedied without conducting an election under a different system.)
That leaves the proportional representation option
And there could be a substantive complaint about legitimacy if what can be fairly criticized as a false majority under one system is used as the sole basis either for preserving that system, or for imposing another one.
Cullen's suggestion then responds to that concern. But I'll argue that it also implicitly answers the question of what more than a bare Parliamentary majority should be required to make electoral reform legitimate beyond reasonable complaint.
As I've noted before, it would be utter folly to demand unanimous support among all parties or MPs before any change could be implemented. But in assessing our electoral options, there's no reason to question the validity of a system which would be able to earn majority support in Parliament regardless of the structure in place at the time the election process is amended. (And similarly, there's no plausible basis to insist on retaining a system which can be replaced based on that multiple-majority support, no matter how much one party shrieks about wanting to preserve its advantages.)
Of course, it remains to be seen whether the Libs will follow through on Cullen's proposal. But if they do, it should ensure both a more inclusive discussion of Canada's electoral system, and a more legitimate result.
[Edit: Fixed wording, and see correction above.]