If the game is using tactical strategy, hexes are the way to go. Think of the Avalon Hill tactical wargames of the 80's (keep in mind not all were one unit per tile, one example was a game called War and Peace, a Napoleonic simulation between 1805-1815). The only problem is that the AI needs alot of improvement. They should add supply, attrition, flanking attacks (attacking a unit from a behind or in the flank), rout, and pursuit rules. Let's make the game more complicated, smarten it up a bit.
It is funny the designers have added hexes and 1UPT but have never played a tactical wargame in their life, except for perhaps Panzer General (if they were lucky).