U.S./European tensions over the war on terror are really over how to fight it. The Europeans (even some who are working closely with us) think a "law enforcement" approach would work better than a "military" one. The reasoning is that they recently defeated their domestic terrorists (Red Brigades, Bader-Meinhoff, IRA, ETA, etc.) using the law enforcement approach. This approach denied any possibility of conceding legitimacy to the rebels by declaring that it was a "war," and doesn't open the whole can of worms about who's a "legitimate" and who's an "illegal" combatant.
One could make a case that this worked well in Afghanistan. We asked the Taliban to extradite certain criminals. When they refused, we got UN sanction to intervene, using military forces because ordinary law enforcement resources were unsuited to the task. However, all this was expedited by the September 11, 2001 attacks. Without that motivation, the UN would still be debating the issue.
Of course, the Europeans also have more police muscle than the United States. These consist of paramilitary law enforcement agencies, "secret police" (like the masked cops who recently busted the Mafia boss in Sicily, and operated against the IRA in Ulster), stringent anti-terrorism and criminal conspiracy laws, and no posse comitatus act (which prevents the American military from doing any domestic law enforcement work).
The Europeans believe that, even against terrorists possessing a base in another country (like al Qaeda in Afghanistan in 2001), the police methods would still work. This may be true, but it also reveals another European trait, fear of taking the initiative. Europeans are much more risk-averse than Americans. This can be seen in many areas of life, from medicine to business practices. As a result, Europeans see Americans as "reckless", while Americans view Europeans as "timid cowards." Early in the 20th century, Europeans were more adventurous, but that brought about two World Wars, and major thugs like Hitler and Stalin.
The Europeans see themselves as the end result of thousands of years of cultural development. What they avoid admitting is that America is basically an offshoot of that same European culture, but one that ran far ahead of the pack. The most obvious result of that was the first modern democracy (the United States) in the late 18th century, followed by an industrial revolution that, by the late 19th century, was the biggest job producing system the world has ever seen. Europeans don't like to accept the idea Americans have outdone them, because the American attitudes, although derived from European roots, are so different from what the folks back in the "old country" believe. None of this is admitted officially, but go into a pub or cafe, and ask around.