Lots of them mention having a great product that solves a real problem, having a content-rich blog to drive traffic, inviting friends and some PR. (Maybe the friends one isn't so applicable to an ad network!)
Convincing business owners to invest in advertising that is not being served anywhere would be difficult, even if CPC-only.
i suggest you to go and check Kilometer's blog. Kilometer is now building a new startup, and they are documenting their journey from an idea to 1000 customers. http://www.kilometer.io/blog/
Contact as may publishers as you can and offer them INSANE payouts for serving your ads. That way you get some initial movement.
Then go to Affiliate Marketing Forums and promote your traffic source there. Affiliates will eat it up if you manage to get some volume.
Affiliates are eager to test out virgin traffic sources.