The fact it can't learn is a possible problem in terms of not being able to adapt to players specific strengths and weaknesses and "go easy" on players it beats.
Actually, I think it's impossible to crate AI strong enough to be really challenging even for a beginner. After you grasp basic rules, it's not hard to outsmart AI. And in my opinion AI, that actually require you to think is much more fun to play, than the one, that can beat you only with huge initial advantage (eg. current Insane SP challenge).
Also I would like to extend an idea, that was mentioned before. It might be interesting to create several AI's each for a specific settings, and then combine them together. So for example, there would be separate AI used for FFA's, 1v1 games, team games, maybe even different ones for game witch cards or full distribution/warlord distribution.
in this way, each person could write part of the code and create together AI that is versatile.