I've found Facebook adds work well to build up a Facebook page (get more likes,) but as to actual conversion to iOS app sales, eh, I think I agree with the general consensus here, that it doesn't work.
If you're going to put some money in to a campaign, it seems more cost-effective to do it through a service like Appsfire or Tapjoy. The CPC is comparable to Facebook and you only pay per install. However, although it's self-service like Facebook ads (mostly, they're very helpful if you have questions in my experience) it requires some forethought - you have to integrate the SDK into the build, and if you already have an app on the market it'll have to be in an update. Also, your budget will matter - if you have $$ to get enough downloads to push it up the charts, and convert some free downloads into in app purchases or paid version downloads, then it'll be worth it for exposure, but i'm not sure smaller (under $100) budgets work with this route.
Chubbs- Have you ever tried reaching out to reviewers? I imagine it's harder with utility apps than with games, but I was curious if that was your next experiment in marketing.