Al Qaeda is more comfortable in Yemen than in Pakistan, at least for Arabs. It's also safer, for the moment, as the Americans don't have as effective an intelligence network as in Pakistan and Afghanistan. Arabs are not popular over there, where Arabs tend to look down on the Pushtun tribesmen, and the Pushtun retaliate by taking cash or favors for information about where Arab al Qaeda are. In Yemen, there are only Arab tribes, and many of them will shelter and protect Arab al Qaeda, or even non-Arab terrorists (if the guest is sufficiently grateful and respectful of superior Arab culture). So while the U.S. UAVs are not finding as many targets in Yemen, there is still danger from Yemeni troops carrying guns and arrest warrants. The tribes can successfully resist these arrest orders, since most adult men in Yemen are armed, and belongs to a tribe. But having sanctuary in a tribe limits how far you can travel safely. Leave the limits of the tribe's gunmen, and you risk encountering police or soldiers who will arrest you, and shoot to kill if you resist. Al Qaeda has taken losses every month from members who left their tribal comfort zone and got shot by security forces.
It's become more difficult for Arabs to get into and out of Yemen. Since Yemen based terrorists recently tried to ship bombs via air freight out of Yemen, passengers and cargo coming out of the region are subject to more intense scrutiny. Forged documents are more intensely scrutinized and less likely to Arab looking men through security. The alternative is a longer trip via ship from Karachi, Pakistan to a Yemen port.
Newly arrived Western diplomats quickly learn that al Qaeda and Islamic terrorism is not, and will never be, the top priority for the Yemeni government. Poverty, water shortages, unemployment, corruption and tribal politics always take precedence. The U.S. and neighboring Arab governments, offer lots of cash to get the attention of the Yemeni government, but it's never enough. That's because for many of the tribal leaders, honor and ancient feuds are also in play, and with those situations, cash dulls the pain temporarily, but does not provide a permanent fix. In times past, you got the tribe's attention by killing many members, and threatening to keep at it unless some cooperation was forthcoming. Egyptian troops, taking sides in a 1960s civil war, played this way, using chemical weapons to make the point. But this sort of thing is no longer tolerated, and the tribes know it. New solutions are still being sought, and the wealthy and powerful foreigners are frustrated with the limited abilities of the Yemeni government (which never had a lot of power in the past.)
Even without al Qaeda showing up looking for a sanctuary, the Yemeni government would still have had problems with its independent minded tribes. The additional cash coming in for economic development and counter-terrorism causes additional problems with the tribes, because the government officials always grab a portion of any incoming funds. Tribal leaders usually believe the officials take too much and the tribal worthies get too little. Moreover, the tribal leaders have more immediate need (unemployed, underfed and sick members of their tribe), and all those guys with guns.
The growing violence, largely organized by Islamic terrorists recruited by al Qaeda, is not popular. But because al Qaeda says it is defending Islam and tribal honor, it's difficult to oppose the ambushes, roadside and suicide bomb attacks and kidnappings. But when you start shooting at soldiers and police, the security forces shoot back and enemies are made as the casualties increase. Blood feuds are popular in Yemen.
The government is using a combination of troops (usually just for show, to intimidate tribal gunmen) and gifts (cash and goods for tribal leaders). The gifts are best accompanied by having someone of sufficient stature sitting and talking for hours, drinking tea and getting to know who was feeling how about what and why. Even a bribe can backfire if given incorrectly.
Inside the capital, it's open season on al Qaeda operatives. That's because the Islamic terror group is actively trying to kill government leaders and foreigners. Four CIA employees barely escaped injury when a roadside bomb went off near their vehicle. Out in the hills, al Qaeda organized gangs are carrying out most of the ambushes of troops.