I love stuff like this. There was a Dungeons and Dragons direct to dvd release that I had a lot of fun with (my CYOA collection was only dwarfed by my D&D Endless Quest book collection...I still have nearly all of them). And, as srbclarke mentioned, the old laserdisc games were great, for those who like this sort of thing. There was also the early PC CD-ROM wave of "interactive movies"...stuff like the 7th Guest or Phantasmagoria which featured puzzle/adventure games chock full of live-action cutscenes. They fell out of fashion, which is a shame, because they could be done really well now.
Maybe the way to do it would be to release a feature film, normal, traditional style movie. Then a web/dvd release of an interactive version. When you get to "choice" screens, you can make it even more interactive with little puzzle/mini-game sort of things (again, see the puzzles in 7th Guest, etc). How well you do on the game can affect the scene you get to watch next...how well your choice worked. The drawback to this? It would be a LONG and expensive production. You'd need a ton of footage and exponentially more edited scenes than you would for a standard movie.
I'll have to check out the Outbreak game when I get home. Sounds like something I'd enjoy. I think doing a niche genre (zombie attack, fantasy, sci-fi) would be the way to go if you want to do something like this. As great as it would be, I don't think it would be mainstream popular, though who knows! I think it would be awesome doing something like this!