I think there are a few things here that cause this:
a) You're going against the worst kind of incumbent- the 15 year old nephew or kid next door. He's cheaper, good enough, and "trusted". He is competition that exists a million times over.
b) Even if your system is better, they just can't be bothered to even get a good demo. You definitely need to build something so usable and good it's frightening, but good luck getting the full demo.
c) The guys that do have the ability to get in with a demo (GoDaddy, yellow pages,etc.) have no clue how to sell something good. What they usually sell is usually crappy, so now you have a fearful restaurant owner.
d) To crack this market it's a "heavy startup". It requires lots of capital, it requires sales, and it requires marketing. That's something guys like us don't like to often venture into. It's the same reason GroupOn requires lots of capital and other business like ReachLocal have feet on the street.
e) Churn is miserable. If you're on a monthly fee or provide additional services, good luck keeping the customer. ReachLocal has something like 80% churn,not retention, fucking churn.
Here's how I'd go about this for months 1-9. Crack the nut of an easy to use system (point b) and find distribution channels that already exist (point c) such as local newspapers, print shops, and others with a foot into the local market. You'd also need to have a system of people to crank out onboarding in a very cost efficient and systematic manner.