Bob,

As you said, legitimacy lay in the hand of the people. So in COIN, as it is practiced nowadays, the question would be is it possible to build legitimacy? (And I do not have the answer).
The question may seems genuine as if you take the postulate that legitimacy is built through democracy then you run elections and you have a legitimate government.
But to that I see several constraints or contradictions:
- In recent past, we tried to build legitimacy by picking up individuals as our champions, gave them means to be elected but in fact did not make any real populace consultation as the democratic process was tricked at the early stage. So the legitimacy of the elected body is extremely questionable.
- If you have an elected body recognised by 51% of a population but controlling less than 49% of a territory: he is legitimate but unable to administrate.
- If the elites of a selected place do not recognise the democratic process as legitimate. You end up with a governmental body which is not capable to administrate and incapable to deliver services. Then you loose the capacity to enjoy its legitimacy.

A combinasion of those constraints may even make the problematic of building government legitimacy even more complex...