Starcraft AI is also a bad example for "good" AI, when we're talking about a game with extremely rudimentary resource collection and where it's all about build orders. The AI can be honed to do very well at such mechanical gameplay, but it's substantially less complex than any Civilization game, and therefore a far cry from what all-aspect strategic gameplay would require.
I agree that the challenges involved in programming the CivBE AI is far greater than some collect-build-rush-repeat game. However, I think there is some value to the comparison. A Civilization game inevitably breaks down into microcosms of tactics underlying the general strategy. While there may be some difficult programming problems in leading the AI to recognize these situations, once they are identified, the parameters of strong courses of action are similarly easy to define as Brood Wars (or any other similarly mechanical, twitch reflex RTS).
[I apologize for forgetting who suggested this idea and not properly referencing them] It was mentioned that once an AI unit comes within a certain distance of an enemy that an algorithm isolates a 10 X 10 Hex Square and runs some preset number of iterations to determine the statistically best course of action. In other words, there are solutions that would cause the AI not to send outnumbered, technologically inferior units to a pointless death.
IMO the main issue is a strategic level algorithm for the AI that determines the proper tactical algorithm. The individual tactical algorithms in-and-of-themselves are relatively simple. Its when there is a complicated strategic overlay on top that makes it difficult. You can write a large volume of tactical solutions that we discover consistently on these forums. But if each situation is addressed (almost) separately the programming becomes too dysfunctional to run. Determining the overlap as opposed to an entire separate set of instruction lines- to for ex. stock carriers with fighters- is a major challenge in a game this complicated