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.

In addition, see my thread 'Secret Deployment Deck' Aug 26.

I agree that most players are concerned with 'variation' of the decks.