The most common complaint that I've heard from people after playing quite a few times is that the deck that you build is, more or less, going to be the same each time you play as a specific faction. For example, if you are playing the Undead, every time you play you will have some combination of the 4 basic units in your deck, plus a mix of a very few select neutral cards. This doesn't leave for much variation on repeats.
An idea to mix up the decks a bit, is to add in extra unit cards that you choose before playing. For example, an expansion could include 4 new units per faction, and before the game starts, each player selects 4 of the units to put into their decks, with restrictions being that you have to have one of each "category" of unit (a level 1, 2, 3 and 4 unit). Different types of strongholds with different abilities could also be chosen beforehand. This would mix up the "base" deck quite a bit, and make for some interesting variation.