I think what impresses non-technologists the most is if you have a full and utter grasp of their business, not just their product offerings. You can show great prescience if you can thoroughly research their products and say things like "I bet your customers have said that they wish they had x feature", or "Have you considered y alternate method to monetizing your core product?". Chances are, all the ideas you toss out they will have thought of, but it will show that you're in the business of helping them get to business solutions and not just build them some cool software. This will make them feel like you're on their team, and greatly increase the chance of landing a contract.
Consequently, if you find this part to be difficult (extracting the core business that someone is in from their product offerings) then it becomes more and more difficult to pitch technology solutions, since you're basically missing the whole point of their company and just attacking their pain points from the outside->in. Whoever is in the role of gathering contracts should be able to direct all of your technological forces into a business solutions package, instead of a technological solutions package.
One of the things I do is troll Craigslist off and on. We have a contract right now valued around $90k from a single phone call to a poorly written craigslist ad that I reached out to. Not bad for literally about 30 minutes of a phone call and 90 minutes of discussions and negotiations.
No one will represent you the way you can if you are willing to learn some skills, but sometimes you need the outside help. However, a little mentoring/guidance can go a long way if you are willing.
In the end work will not find you guys until you have a niche and decent reputation, and even then people who say they never look for clients I think are not being totally honest. I met with one successful and smart guy who runs a consultancy and he swears he never looks for work it "just finds him". Well, that is sort of true but not really the whole truth or being totally honest. Specifically in his case, he does a lot of tech training, writing and is involved in a specific tech scene. So in the end he is doing a ton of marketing and talking about his team and their abilities, he's just not out cold calling or using a lot of traditional marketing.
Also, consulting can enter into feast or famine mode unless you designate someone to keep deal flow moving. This isn't optional and can't be something you do half hearted. It takes dedication, but it doesn't have to be sole sucking shit work, it should be fun and be a lot about pre-sales and pre-qualification of clients. It can even be something that is a shared duty but it has to be dedicated time every week.
Developers many (maybe most) times get to wrapped up in the details of the project and forget to close the deal first, leading the clients to "take advantage" of you. We have all done it and still do it from time to time. It is smart to use a pre-qualification interview of a few questions. You don't do it in the "interview" style, but you get some qualifying questions in so you can frame the project to see if it is even a decent match before you put too much time into it. Budget and timeframe are the two critical keys to get out in the open early, which generally prevents a huge portion of wasted time on both sides. Not only that, it has let me refer leads to other shops/developers that might be a better fit and then I will get a referral fee. Likewise, I happily pay referral fees to others who send clients my way.
One of the things that we have been caught up in before is a continuous sales cycle where the client has no intention of actually committing to picking up our services but rather is seeing how much pre-consulting work they can get out of us. This has only happened a couple of times in our history but when it does it is costly to whoever is working the sale as it's not really a salaried deal with us. So we get a little gun shy about extensive pre-sales. As well we are trying to move away from a contracting / consulting service and into something that we have some ownership of.