I'm a big fan of CYOA books (especially the old Steve Jackson ones). You could probably find a niche market for CYOA video, sure. I'm tempted to do one, too.
About a year ago, someone on the forums posted their CYOA attempt. It was pretty basic, but the mechanics for it are already built into YouTube - stopping playback automatically at pre-determined points, and URL t= overlays for choices. I'll see if I can find that thread.
.