an armed rebellion that enjoys a broad base of popular support.
Bob, those are the words that YOU used and I don't think that you can credibly argue that 5% or even 10% = a "...broad base of popular support..." In fact, in Malaya, the lack of the broad base was one of the key reasons that the COIN campaign was so successful and why perhaps so many derived so many false lessons from that campaign.

Fact is that these are populaces that were denied legal, effective means to affect change of government in every case listed; so they were forced to take illegal approaches to advance their concerns.
Popular myth does not equal fact: your statement above is not correct other than in that there are always disaffected elements in every society who seek to circumvent the due processes...in each of the examples i gave they DID exists workables means for affecting change: the 'insurgents' were only forced into the methods they adopted because they DID NOT enjoy the level of popular support that would have made legitimate means feasible for them...Hungary 56 and Prague 68 would be better examples to support your 'argument'...

That is why COIN really just very very rarely would ever fall into a category where one would approach it with best effect through warfare.
Correct but only in that a fundamental aspect of COIN is the need for a comprehensive approach (UK/Commonwealth) or unified action (US) that harnesses broader instruments of national power to achieve national strategic objectives. ONE of this is military force: if there was no need in a specific scenario for the application, or threat, of force to achieve those objectives then it wouldn't (yet) be a COIN campaign - it would be law enforcement or perhaps internal security...at most, perhaps, FID...