I've tried a few games with some friends and we seemed to find that whoever had more in the terror department seemed to dominate the game. The last time we played, I got out a few characters with Terror early and my opponent didn't even have a chance to come away with the game. Is this normal or bad luck?

Well, I think with more play you will find that terror is not overwhelming. For one, you can't drive a terrifying creature insane. For another, you don't have to commit to stories unless you can afford one of your characters to go insane and you still have enough stuff left over to get something done at the story. So sometimes building up before committing can be very useful.

Plus, having a character out for 2 turns isn't game breaking - compare to combat where a wound can remove a character from play for good (unless ressurected or something, of course).

When I first started playing I thought terrify was a big deal, but the more I played the more I saw the balance.

Don't forget the game is about winning stories, not beating up characters! :-)

but after you beat up every opposing character (= noone will defend against you on stories.. hehe..

And yeah at first glance terror sounds very nice, but when you play more, and more.. you will find lots of guys with Willpower against you, or got all your icons removed, or scary monsters shoot of with shotguns =

From the Core Set, Mad Genius (Miskatonic) + Arkham Asylum is good for taking those Terror losses .

It's all in how you play it. Some decks make opponents cry "Investigate is Overpowered!", other decks have no characters so don't care about terror, and (at least in the old-school CCG) you can make a great madness deck which works best on opponents who have terror (as Willpower is significantly harder to remove)!