I think a great option for them would be to release a new edition of the game with four new factions and 12 new tiles.
Say, Astra Militarum, Necrons, Tyranids and Tau.
That way it's a great new product and at the same time it's a fantastic pick up for those who already love the base game and want to mix and match races and titles. I think it should definitely stay at max four players though, the Planning Phase is great and relatively interactive but combat between two players leaves the other two completely out of the loop. I use a house rule where other players can go ahead with non-advance orders while others are doing combat, if they're next to go and have something on top of a stack.
I would also love to see "faction expansion packs" that interact and replace or add to the decks for the standing races. For example I'd love a Space Wolves faction expansion that combined with the Space Marines faction and added a space wolf combat deck (scouts become blood claws, space marines become Grey Hunters etc), a new faction card (the big one, and a dominate ability) as well as thematic new space wolf upgrades. These could be as intensive or as light as they like, for example even just a few simple combat cards and upgrade cards might suffice, or they could go balls to the wall and release a whole new set of light blue figures, (land raider would probably be a Thunderwolf rider or a wolf claw equipped Dreadnought) Or they could just use most of the blue space marine figures and simply add in the dreadnought piece and it's supporting upgrades and combat cards.
Ideas for action expansion packs/replacements
Space Marines - Space Wolves, Blood Angels
Chaos - Thousand Sons, Death Guard
Eldar - Dark Eldar
Orks - Evil Sunz (Speed Freakz),
I think another good idea for an expansion ties in with another aspect of 40k that always does well - characters. Adding some battle changing and influential characters to this game could shake things up quite well. The Eldar could have a devastating Avatar of Khaine (strong combat) causing havoc, the Space Marines a strategic genius Chapter Master (buffs), Chaos a powerful and cunning sorcerer (opponent affecting effects) and the Orks of course would be a powerful Warboss (Unit creation).
I'd also just be happy with entirely new races. The colours would be hard though, Necrons would work well as a dark charcoal grey, Tau would be orange, Nids would be a purple/magenta and Astra Militarum would be khaki of course!
Just some ideas.