Working on a very young lean startup and as we've gotten off the ground we've struggled with these problems. We'd ask what they were looking for and we heard about big integrated solutions and lots of little (low value?) features. It didn't seem like this was leading us in a lean direction at all.
What we ended up finding much more valuable was to identify specific hypotheses about the problem we were trying to solve. And then set up a specific "experiment" to test our hypothesis.
An example would be helpful: our original idea was that we would make a system for collecting conference session evaluations -- replace the paper eval forms with a web/smartphone based version. We identified conference organizers as our market. Thus our first hypothesis to test was, conference organizers care about collecting session feedback.
We called and emailed a bunch of conference organizers with a really quick questionaire: do you collect feedback? how? what do you do with it? how much do you spend on it?
That's it. At the end of 10 responses, it was totally clear that we were barking up the wrong tree. Pivot.