I am in computer science (machine intelligence and human-computer interaction). I haven't looked in depth at Civ5's AI, but here's a few guesses as to why the game design might have made AI-design harder than Civ4.
- With 1UPT, you can't just have a heuristic about the kind of mix of stack you want to send. Instead, the AI now also has to pick between various different configurations of troops on the ground with respect to the varied different kinds of threats that could flank them, etc. Panzer General might have a good AI for that, but the makers of Panzer General presumably only needed their AI to do that -- they didn't also need to build a solid AI for all the other aspects of the game too. (The Civ5 team probably were a bit pushed for time).
- Global happiness also makes things a bit more complex -- previously a city governor could just optimise its individual city; now the optimisation has to be across the whole empire.
- Border expansion can now be directed at will (buy a finger of tiles to grab that resource), making resource capture harder for an AI to predict.
- Skewing your empire temporarily in any direction can trigger a significant one-time benefit. (Run happiness to get a golden age; culture-spam for a new policy; spam military for a one-time war; spam cities to zero happiness in preparation to build or buy a splurge of happiness buildings in them) Because there are quantised trigger-levels, you are best off going hell-for-leather at one of them, ignoring the others, then switching, rather than taking a balanced approach. You are usually better off going all-out to get benefit A at t=5 and then all-out to get benefit B at t=10, rather than taking a balanced approach and triggering both at t=10. That can "feel" bad if an AI does it. It also means it's harder for an AI to exploit your situation or infer your longer-term goals, because you will suddenly switch track after you've triggered the policy / golden age, etc.
- Diplomacy is less clear (no religious alignments) and involves more participants (every city state).
- As every city now defends itself, the human player no longer gets caught in the trap where they neglected military to try to get a tech jump, and a stack of Mongols turn up unannounced. It now takes enough turns for the Mongols to do damage that the human can use the AI's tactical and strategic limitations to defeat an invasion even starting from almost no troops. That could make the AI feel less effective.
The problem is that each of these changes gives rise to new strategies that can take significant advantage of them, and these strategies are quite different to previous Civ games. The AI to use these strategies is achievable (though they ran out of time). The AI to detect a human player using these strategies is harder. The AI to detect a human player using these strategies and foil their plans is very difficult for some of these mechanics. And that means that when you play you usually feel like the AI is being "dumb" because it always seems you are catching it unawares.
Anyway, that's my blind guess from just playing half a game of Civ 5 so far!
PS. As an addendum, it is worth remembering that Soren Johnson, Civ4's designer, was Civ3's lead AI programmer. It's not so surprising, then, that the Civ4 game mechanics are easier to design a good-feeling AI around!