I've been running an ad in a small weekly newspaper for the past 4 months named the Bargain Bulletin. Costs me $5/week. I've gotten around 3-4 calls per month from it. The rest of my customers have come from flyer dropoffs in paperboxes and tear-off sheets placed around town, which i print myself. But have yet to see any steady stream of customers. I will go some weeks and not get any calls at all.
I'm glad to hear that the Yellow Pages have helped a couple people, since I put my ad in there too. The next one doesn't come out till May though, so I won't know if it works till then.
A guy approached me about a month ago about showcasing my ad in a restaurant up on a board alongside the specials. It's gonna cost me $150 for the whole year. I'll see if it pays off.
Two other ideas I will be trying soon are placing yard signs at busy intersections, and finding out what the newspaper charges to put my flier in there just loosely. I will be back to report my results.