It certainly is a war game, Rome expanded via conquest, how else? To say it isn't is just semantics.
But Azugal, you're arguing about execution. The next game that Paradox makes perhaps, on a different engine, can be built from the ground up to not use province movement.
And minimal game? I would say revolutionary. Remember that was why Rome Total War was so highly lauded over MTW, the freer movement.
AI admitely don't get a lot of attention in games, but certainly if it can be done well, then a free movement model would be much superior.
Think about it for a second. If war becomes more... interactive, then Paradox could possibly find a bigger audience outside of the spreadsheet crowd without losing anything that made their games great in the first place (which IMO is the excellent implementation of real time strategy). I think that's good for the company, and then maybe they will be able to afford a few more AI coders then.
@shasla6, who are you talking to?
@basharious, but you must admit that there would be more depth in a non-province movement system. If you get bored with the intricacies, then don't bother. Just send all your men across.

If you have overwhelming superiority human wave attacks work well too!