Magic by nature is powerful but volatile and always has the chance to fizzle. Witchdoctors have staves that can hit multiple enemies at once with the potential to deal massive damage with the super and epic hits you mentioned. Since that potential damage is so high, it needs to be tempered with a fizzle chance so that, over time, the Witchdoctor's damage output stays in line with the other classes.
I am a level 57 witchdoctor and the last time I frizzled was at level13 I believe. I think that the problem is that you are using aoe staffs. Staffs have a greater chance of frizzling. This is why I always use wands, not just for their low frizzle chance, but for their range. So, my tip is to use wands or a staffy/shooty weapon.
You can always increase the chance of a spell hitting by increasing your Accuracy and the damage it does by increasing your Will. Usually, the only fizzles you get are when you are trying a direct attack instead of using one of the Powers/Talents you have.