Because there aren't a lot of companies that would want to invest the resources that it would take to compete with Civ. Civ is complicated game with a lot of depth (though it doesn't always feel like that) and you can't really "bootstrap" your way into success in the video games industry against that kind of game anymore. If a company really wants to make a "Civ Killer"* then they'd need to make the same kind of investment into their game that Firaxis/2K does into Civ** and that mostly sounds like a great way to loose a lot of money. I'd be curious to know that Millennia's staff and budget were because it feels like Paradox/C-Prompt lowballed both.
*Or even just a serious competitor.
**Honestly, they'd probably have to out invest Firaxis/2K.
Anybody trying to produce a successful (i.e., many sales, much money) 4X historicalish game like Civ runs into three basic problems:
1. Avoid making the same mistakes that Civ and other such games have already made: no visual identification with the Civ like Humankind, lousy AI as in Civ, late-game micromanagement in everything, etc. Guaranteed you will get called out on that Immediately.
2. Do something to distinguish your game from Civ, which is the 'standard' against which any new game in the genre will be measured. IF your game is simply a Civ Clone, why bother? If you do something wildly new and it is implemented poorly (which, I propose, is Millennia's problem in many ways) it will simply turn gamers back to Civ. This is a very difficult balance to maintain, because of the other problem general to game design:
3. For all the talk of Development Teams, my observation is that most games come down to implementing one Prime Mover's vision of the game. This is, by the way, in ALL gaming. Strategic board games when they started out back in the 1960s and 1970s could be easily identified largely by whether they were designed by Roberts (founder of Avalon-Hill), Jim Dunnigan at Poultroon Press/Simulations Publications, or Frank Chadwick at Game Designer's Workshop. In Computer games, Sid Meyer is the prime example of a Prime Mover who haas influenced an entire genre (4X) of gaming, but Brian, Jon, et al have also made their marks. Some of these people are very, very good at what they do, but as computer games get more complex and demanding, they are starting to exceed one man's capacity to keep everything at the same level of excellence. When you are also trying to avoid multiple pitfalls from previous games and distinguish your game from another, the pressure becomes enormous.
Millennia, as far as I can see, suffers a bit from all three. It makes basic mistakes that could have been avoided just by paying attention to other games; it repeats several Civ mistakes that are very annoying to see come up again; and the final game gives the impression (as others have remarked) that it is not quite finished, and given Paradox's history, makes one fear that we are going to have to pay more to ever get a finished product.