I love building software and serving people but don't like giving up my IP and doing the same work over and over again, so I'm actually shifting out of consulting and into product development.
But if I were starting over, this is what I'd do:
Call them up and ask them. Seriously! Yeah, I know, maybe 8 or 9 out of 10 calls will be dead ends, but you miss 100% of the shots you don't take. If you feel really awkward about this, you can say at first that you're doing a research study, or you're interested in their industry and want to learn about it, or whatever pretense you feel comfortable with. Just have a casual conversation, get some rapport, and find out what the person does on a day to day basis and what kind of things they hate doing or wish they didn't have to.
Do this enough times, refine your methods, and you'll get really good at identifying business problems that you can solve with technology.
Don't waste your time with struggling small businesses; call people who have money. Find people who are superstars in their industry. Or if you really want to work with small businesses, get into the business of teaching them how to be good at sales and marketing (so that they'll have money :) ).
A great question (once you have rapport) is: "Think about the last 10 or 20 emails you dealt with today. What were they about? What did you have to do?"
Once you find pain, lock onto it like a heat-seeking missile and dig deep to find out what's causing it, what the effects are on the bottom line, and what the emotional impact is on the person you're talking to. Is this something so painful that it's affecting their relationship with their family? Solve that one for them and they'll start treating you like family!
You only really need to do this once or twice before you start getting referrals from deliriously happy customers. You suddenly become the "go-to" guy. Raise your rates.
Everything I've said can be applied to creating a product business, too. The change is that you need to interview many people in the same industry (or profession) and get them on board with a product idea that will solve their common problem (i.e. validate the idea before you build it). I'm in the process of doing this right now within a certain service industry niche.
My email address is in my profile here, and of course I'm happy to answer questions or point you to helpful resources.