U.S. troops who have served in Iraq, and now find themselves in Afghanistan, are discovering some similarities. Mainly the corrupt and inept police found in both countries. But not only does Afghanistan lack an effective national police force, it has never had one before. Moreover, the tribes have evolved a crude justice system over the centuries, and where that system is in force (many areas of the country are just plain "lawless" except for tribal justice), there is hostility, often armed hostility, to outsiders (Afghan national police) trying to come in and displace tribal power. Recruiting police locally sometimes works, but you have to accept the fact that tribal leaders will have great influence over subsequent police actions.
All the tribes want from the central government is autonomy, and a share of any money foreign governments are giving to "Afghanistan". This has always been a sore point with the tribes. In dealing with the foreigners, large bribes or gifts (it's often difficult to tell the difference) are often given to the leaders of the country, in return for some favor (like assisting in fighting international Islamic terrorism). The tribes, even when they have some of their own people in the national government (the current Afghan president comes from a family that has long produced tribal leaders), don't trust those guys in Kabul to share the foreign loot fairly. This is a reminder that the politics within tribes can get pretty nasty. That's why some tribes have pro and anti Taliban factions.
The problem with the police in Iraq was that Saddam did not give the police much authority. They could handle traffic and any crimes not committed by government officials or Baath party members (these were handled by one of Saddam's secret police organizations.) Over time, it was possible to improve the quality of Iraqi police. More training worked because most Iraqis were literate, and most Iraqis were familiar with modern police procedures (either from kin in Europe or North America, or American TV shows). Not so in Afghanistan, where most adults are illiterate and many of those who have seen American TV consider the crime shows just more escapist fantasy (so do many Americans, but that's another story.)
So what's to be done? The Americans would do well to look across the border at how the Pakistani government polices their Pushtun tribes. Not only do the Pakistanis have twice as many Pushtuns to cope with, but they have been keeping the (what passes for) peace in the tribal territories for over 60 years. They carried on many techniques developed by the British, who in turn studied the history of the region and, eventually, realized you had to be creative in policing the Pushtuns.
What the Pakistanis use are a combination of paramilitary regiments (recruited locally, and usually named after the dominant tribe, as in the Afridi Rifles near the Khyber pass) and traditional tribal policing methods. The key is to respect the authority of the tribal leadership. While it's true that this leadership may often be corrupt, ineffective or split by violent feuds, it's important that the tribes don't automatically see the government as the enemy. The paramilitary forces help keep the peace between tribes, and go after outlaws (lots of outlaws in the tribal territories).
Meanwhile, across the line in Afghanistan, too many of the cops are the outlaws, and the U.S. troops have to act as the police. Meanwhile, many of the police commanders, who are literate (often university graduates) and aware of modern police methods, are also familiar of how the Pakistanis operate. Thus the Afghan police are evolving, and the speed of change depends on the quality of the commanders (some are patronage appointees, but others are eager to become professional police.) Welcome to the tribal territories.