From this story I have to say that it is difficult to get meaningful conclusions from the google adwords research tool when the idea is very niche and original. Also talking with random ppl on starbucks wouldn't get me anywhere. The splash "coming-soon" site with email sign up for site updates is one of the best tips I've heard so far (read it first on the start-small-stay-small book), but that kinds of requires commitment to start developing, leaves a lot to subjectivity on what conclusions could I reach to if after a month I have X email addresses from interested visitors, and who will come to visit an empty splash site and leave their email anyways?
Anyhow I don't think there is any easy solution for this, but if you can provide tips either in here or in the question they will be welcomed.
When I do web products, the UX, I'll create a wireframe/mockup then find people and ask the question, "How would you do X". Then see how they think through the interface. After a couple iterations I'll create a quick web app to test varying hypotheses.
Another tip, I do this when forming a pricing strategy, is to form a few cases (X price with Y features). Then see which the person picks or test one at a time and see which gets the most responses. You can do DOE or multivariate analysis and come up with a near optimal solution.
If you're interested in this idea you'll likely find value in reading the book.