Bob,

AQ drew upon the the very high conditions of insurgency in those states and drew upon the sub-populaces who were most dissatisfied with their own governments. They traveled to Iraq not to help make Iraq part of some "Caliphate," but rather to help defeat this source of foreign influence so that they could finally find some success at home.
I think you need to revisit what AQ did in those countries. Yes, they wanted to kill the foreign infidel and drive them out of "Muslim lands." But more than that they wanted to purge the apostates. Look at the actual operations conducted by AQ-in-Iraq - they killed so many Muslim Iraqis that even UBL got pissed off at the carnage they caused. I'm not sure how bombing a market full of Shiites helps to defeat the "foreign influence," but maybe someone can explain it to me.