Definitely an image problem...

Rico says that that little 9.11 thing might've contributed to the problem, but Lee Keath has an article in the Philadelphia Inquirer about al-Qaeda's image issues, and Osama bin Laden's laments about them:

During his last months holed up in a villa in Pakistan, one of the concerns on Osama bin Laden's mind was image control: al-Qaeda's branches and allies were making the terror network look bad in the eyes of the Islamic world.
A newly released selection of letters captured in the US raid that killed bin Laden a year ago shows the al-Qaeda leader was meticulous in tracking how his associates' actions and public statements reflected on the cause of jihad, or holy war. And he frequently tried to keep them in line.
In an October of 2010 letter to a top lieutenant, bin Laden complains about Faisal Shahzad, the militant recruited by the Pakistani Taliban to set off a car bomb in New York City's Times Square; the May of 2010 bombing failed. During his trial, Shahzad , a Pakistani who gained US citizenship , told the court he "didn't mean it" when he took his American citizenship oath, which includes a vow not to harm the United States.
But bin Laden said lying about an oath breaks Islamic law. "This is not the kind of lying to the enemy that is permitted. It is treachery," bin Laden wrote. He told his lieutenant to take it up with Hakimullah Mehsud, the leader of the Pakistani Taliban, and ensure it didn't happen again. "You know the negative effects this has if this matter is not resolved and if the mujahideen are not cleared of the suspicion of breaking an oath and treachery."
The letters point to the complicated relationship between bin Laden's al-Qaeda Central and its branches and allies. The Pakistani Taliban are close to al-Qaeda and the branches in Yemen, Iraq, and North Africa use al-Qaeda in their names. But they largely operate independently of the top leadership in Pakistan and Afghanistan, which does not appear to know about most operations beforehand, and offers advice and guidance which is not always heeded.
The seventeen letters released by US officials do not give a full picture of al-Qaeda's operation or of bin Laden. The messages, written by bin Laden and senior associates, are only a small sampling of the trove seized in the raid on the compound in Abbottabad, Pakistan last year.
In his audiotapes to the world over the years, bin Laden was known for his florid rhetoric and highly elevated vocabulary, obscure even to some Arabic speakers. But there is almost none of that in the private messages to associates, and bin Laden is businesslike and to the point, whether it's discussing travel arrangements for his sons, advising Algerian militants to plant tamarind and acacia trees in their desert hideouts (they're cheap, don't need much water, and can hide you from drones), or telling his lieutenants to try to shoot down President Barack Obama's plane on a recent visit to Afghanistan.
He is also unflaggingly polite, even in firm criticism of his "brothers", consistent with the soft-spoken, soothing personality many militants who met him described. He repeatedly prefaces orders with the phrase: It would be good if... And bin Laden appears intent on imposing greater control over the al-Qaida "franchises," though it is not clear he was ever able to do so. He raises alarm that attacks by the branches killing Muslim civilians have "cost the mujahedeen no small amount of sympathy among Muslims. The enemy has exploited the mistakes of the mujahedeen to mar their image among the masses," according to the Arabic originals of the letters posted by West Point's Combatting Terrorism Center.
Once again, he turns to Islamic law, pointing to tatarrus, literally shielding, a set of Shari'a rules on when civilian casualties are acceptable during jihad. The branches are playing too loosely with the rules, he says: They expand what should be an exception allowed "only in extreme necessity" and set off bombs without regard whether Muslim bystanders are likely to die. "First of all, we will be held responsible for this before God Almighty. And in practical terms, it causes great damage to the message of jihad," he wrote in a May of 2010 letter to the same lieutenant, Atiyah Abd al-Rahman, who was himself killed in an August airstrike in the Waziristan region of Pakistan.
Instead, he advised, they should focus on attacking Americans, whether in the US or in countries where the mujahideen would not be vulnerable to retaliation. But al-Qaeda's allies did not necessarily heed the advice. The Pakistani Taliban, for example, are suspected in persistent suicide bombings killing civilians in Pakistan, such as a blast in a market recently that left sixteen dead.
Detailing a plan for an administrative overhaul, by which al-Qaeda's central leadership would weigh in on the naming of the branches' leaders and their deputies , and much like an employer recruiting staff, bin Laden asked that biographies of the candidates be sent to the central leaders. al-Qaeda Central, he says, must issue media guidelines to ensure the branches stayed on message in their statements.
Despite the plan, it is not clear that al-Qaeda Central, or bin Laden's successor Ayman al-Zawahri , managed to bring that increased control. In the letter, bin Laden advises al-Qaeda's branch in Yemen not to get bogged down in trying to fight the Yemeni government to establish an "Islamic state" in the country. Yet since bin Laden's death, al-Qaida militants and their allies in Yemen have been battling with the military over control of several towns in the south of the country.
But bin Laden's annoyance showed whenever anyone goes off message. He chided militant clerics for telling Pakistani victims of devastating floods, which displaced millions in the summer of 2010, that the disaster was punishment for their sins. "It occurred to me too at the time that a main cause of the flood was sin," bin Laden wrote. "But it had to be kept in mind, there were people holding on to two of their children in the floodwaters and losing the rest. It would have been better to focus on talking about rescuing the Muslim victims."
He complains of bad media spin in al-Qaeda in Yemen's plot to bomb a US jetliner on Christmas Day in 2009, which failed when the would-be bomber botched setting off his explosives on the plane; bin Laden points out that the branch said the attempted bombing was in retaliation for a US airstrike in Yemen. They should have said the attack was in support of the Palestinian cause, he said. Such bad messaging, he says: "weakens our position when we say we are an international organization fighting to free Palestine and all the Muslim nations to establish an Islamic caliphate."

and, in addition, there's this:

This undated file booking mugshot, released by the U.S. Marshal's Service, shows Faisal Shahzad, the man convicted of plotting a car bombing in New York City's Times Square. Al-Qaeda's image was a top concern on Osama bin Laden's mind in the last months of his life. In letters captured in the US raid that killed him, the terror leader complains that al-Qaeda branches kill too many Muslim civilians, turning the public against them. He was angered the would-be Times Square bomber broke his US citizenship oath not to harm the United States. "We do not want the mujahedeen to be accused of breaking an oath," bin Laden wrote. (AP Photo/U.S. Marshals Service)

Rico says, no, breaking an oath would be bad.  Killing thousands of people, no problem...