Yeah--Malygos is the one launch legendary I'm pining for.
i got maly not too long ago and ive tried like 7 different decks with it and all of them suck
i only have one ancestors call, so i havent tried that with maly, but i've lost the will to keep messing with it anyways
as far as i can tell, malygos pairs best with cheap aoe spells and spells that can target your opponent directly. so you want to cram a fair number of those into the deck.
but malygos comes into play so late that you need to control/contest the board to some degree for the whole game, which means you need a good roster of minions as well as spells that help accomplish that. but it seems like those spells that help contest board mid game don't generally pair all that well with malygos.
so yeah its a sucky situation
edit: oh yeah and somewhat paradoxically, ive found that spellpower minions suck kinda hard in the malygos decks cause they are not very good at contesting the board in the mid game