Max says it well. You're wanting to look like a real brand.
Um, have you considered BUYING some ads on one website popular within the category? (This is a great time of year; tons of available ad space.)
First, you might sell product with the ads. (Really!) But, also, you're marketing to the marketers if you're on the right sites.
And, really, you can target to a single zip code where a target publisher lives with Google or Yahoo...
Also, get some buzz in your field. Try to get bloggers and even mainstream media to write about your product.
I was the guy who picked out the ads to run on a new website last year. Wanted to be a "big deal." We wanted good looking ads to make the site look like a "player" on the web, to get people to sign up for our free service. I wanted Apple and IBM and Honda. Yeah, right, not on a new site... I didn't do it, but I know people who have put classy ads on their site just to dress it up. Got paid zip.
My point here... are your ads classy? Is the creative sharp? The graphics edgy? New semester is starting, go to your local college and get an ad class to take you on as a project.