Most of the complaining people could have been frustrated by the fact that agility is not a tool-set, nor even a skill-set but truly a mind-set. This mind-set, whose substance is described by the Agile Manifesto, gets derived in many different practices. Therefore, one could imagine that by following these different practices, the project will become transmogrified into an agile gizmo. Unfortunately this does not work this way: as the law is spawned by the spirit of the law, agile practices come from agile minds. You need an agile mind first in order to put agility in practice.
With this mindset, it is possible to adapt agile principles to the sheer reality of your project or your clients, which is where the true challenge resides. Not all clients will accept the full monty: adaptation is needed. Here are some examples:
Your client is addicted to BDUF: discreetly invest “analysis” time in running spike projects (call them “proof of concept”) to tackle as soon as possible all the technological risks and uncertainties (allowing to fail fast if need be),
Your client loves methodologies: turn to Scott Ambler's AgileUP and see how agile the unified process has turned under Scott's expert hands,
Your client does not want to be collocated: release often and expose your client as early and as openly as possible to the system you are building for him (he sure will react and provide an invaluable feedback),
Your client has a really big project, so big that you think agility has touched its limits: then use a more traditional approach (serialization) to pilot agile driven smaller sub-projects (read Balancing Agility and Discipline for more about this).
There are many other situations when it will be difficult or impossible to openly sell an agile project to a client: pair programming (why paying two guys for the job of one?), time & features negotiation (these are the specs: what is the price and the deadline?)...
The important thing to remember is that more than a list of recipes, agility is a state of mind that will materialize differently in each and every project.