Clients want to pay for features not results. Providing the user stories are simple enough to spec and quote for free or the client is prepared to pay for a discovery phase to identify and spec the user stories, I don't think it is an unreasonable request. Why should they pay a programmer for their time and take all the risk rather than paying an agreed price for each feature? Of course you need to make sure the feature is fairly small, the spec is detailed, the client understands that dark matter isn't included, and there are no rocket science or lab experiments involved.
The problem we run into is that while we have pretty good control over the risks in initial development, we have no control over the amount of time taken to demo, explain, tweak and revise the software until the client is happy with it. Because we can develop software so quickly, client contact is a big part of our costs, and to fixed bid a feature, what we really need to know is how many questions the client will ask and how many changes (and of what type) they're going to need to be satisfied.
I'm considering starting to offer a blended approach. After specifying the user stories we provide a fixed price per feature (except for some more nebulous features that may have a discovery cost associated instead). We guarantee to provide software that meets all of the requirements explicitly documented in the story for the price provided. Then of course, the client will want changes. They may want to discuss the software, suggest revisions, see some graphical tweaks and perhaps add some business rules they forgot. Well, because we have no idea how many questions they have or how many changes they want, we'd do that work on an hourly basis.
In this way we can guarantee they'll get what they asked for at a fixed bid within a fixed timeframe with no risk. They in return guarantee that we'll be compensated for however much time they require to get the story to the point that they're happy to launch. We're incented to be efficient in developing the software, and they're incented to value and respect our time (or at least pay for it) in terms of discussions, revisions, training and support.
[UPDATE] related article on InfoQ