People hate abrupt changes to the way they work. So changes have to be introduced, slowly but steadily. Same for introducing agile methodologies to customers. As much as we would all like to believe that the case for agile development, XP in particular, is so strong that all we have to do is "educate" the customer, reality states otherwise. In my experience I have found some customers are very afraid to begin with and there isn't enough time to convince him otherwise before you lose the deal.
So what options do we have? Personally I provide a bridge between customers bduf, spec heavy system of thought and my programmers agile style of development. I am the customer to them. While I provide the specs , with some help, to the people who feel comfortable with documentation. Once the project succeeds I credit it to the agile methodologies and slowly gain enough confidence of the customer to move to increasingly agile system, thereby reducing my role in the process.
Sounds simple? In practice it is often frustrating to act as bridge and be responsible for reams of documentation. Hopefully there will be good tools soon enough to address this space.