Actually the North Vietnamese made a fair amount of progress while they were losing militarily, but that's beside the point...

Insurgencies can certainly exist without a military element. One could reasonably argue that many of the environmental groups (especially those near the fringes) are conducting an insurgency of sorts, as are the anti-globalists. The political element of insurgencies tends to get overlooked in some accounts, so the current trend to emphasize it may be viewed as corrective (although it can go too far in the opposite direction).

Now I want to touch on this for a moment:
To sound like a stuck record, I believe the US Army's (and UK to a lesser extent) problem with COIN is that it is viewed as something difficult and distinct, instead of the bread and butter of contemporary and historic military forces. The fact that this belief persists strongly indicates a lack of understanding as concerns the nature of the enemy, that means people focus on the nature of the conflict instead.
For the US Army, based on its own view of its history and the historical underpinnings of its existence, COIN has never been something it wanted to do. In the early days there was a fear (not necessarily justified) of any standing military force, and an equally dim view of its involvement in anything aside from defending the Republic from an exterior attack. Even when COIN was the main function (the periods after the Mexican War and the Civil War) there was little or no training for the mission at hand. It took Custer's great blunder to even shove them into open-order training and the development of both professional education beyond West Point and the first field maneuvers.

The other thing to keep in mind is that the Army was often viewed as a trained nucleus around which a mighty Volunteer force could grow in time of trouble. It was always small...almost always under 20,000 officers and men. Before the Civil War there was some focus on COIN-type operations, but once most of the officers had tasted the heady wine of a few brevet promotions and major battles, they had difficulty looking back at their actual function in the postwar world. A handful did adapt, but they were few and far between.

This also leads to the second point about the American COIN experience. I focus here on the Indian Wars because that's our COIN heritage. There was always a great deal of tension between the Army and the civilian bureaus that dealt with the friendly tribes (in other words, those not engaged in open warfare with the whites). The Army thought they could manage the process better, and often chaffed at the corruption they saw. During Grant's administration (about 1872) they were cut away from the process almost entirely, with control only coming in very limited circumstances. This forced them to focus on the battlefield aspect of COIN, but also created a subconscious awareness of the cost of inefficient political management. It's lost from time to time, but that awareness does play a role in the collective framework. The complaints you see today about poor civilian planning in Iraq find echoes in the pages of the ANJ during the Indian Wars and the official reports of many officers.

Bit of a ramble, but hopefully it does show that there is a different framework operating when the Army looks at COIN. One reason the Marines may handle it better (or at least quicker) is that their framework is substantially different. Their experiences with civilian control were different, and often confined to diplomatic experiences and representatives as opposed to corrupt or inept Indian agents.