Maybe another way to look at this is: instead of creating a startup to serve veterans or single mothers–why not create a startup that can employ veterans AND single mothers?
One of the biggest problems facing single mothers is the high cost of childcare. In many instances, it makes going to work almost pointless because it eats 50%+ of your paycheck. So, why not a crowdsourcing service (a la mechanical turk/crowdflower) that employs single mothers at home in the United States? (personally I think people would eat that up and even pay a premium for US-based workers)
Veterans could also do crowdsourcing work, on-demand security, and on-demand driving/moving off the top of my head.
Yet another way to tackle this could be to go into an industry that already has the means/access to help these people and partner with them. I'm mainly thinking of education. California's community colleges (there are over 100) cater to these people already. They have night classes and veterans offices. They have programs for in-demand jobs like nursing. Yes, there's the same bureaucratic/regulatory issues since they're a government institution ... but if Starbucks can do a deal with Arizona State, surely a founder who is ambitious enough can get something done.