I played in the local space for a long time in the Minneapolis market. It's tough stuff. Perhaps, as the marketer and not the merchant, I didn't realize the full benefits, but my major road blocks were this:
It's very hard to rank better than the authoritative sites in the local search space. CitySearch, Yahoo Local, InsiderPages, etc., all rank very well for all sorts of terms.
More importantly though was the fact that you are competing with Google itself. Do a search for
Chinese Restaurant Minneapolis and you'll see that the first half of the page is dominated by Google; this happened on thousands of phrases that I was trying to rank for. Getting into the top 5 wasn't generally a problem, but Google's proprietary result (whatever you want to call it) is always on top.