Traffic was relatively high when I started talking to sponsors (~100k uniques/mo). Also, it helps to choose your sponsors widely. A company with low conversion rates that sells a service for low prices needs tons of clicks to justify what they spend on an ad. But a different company — let's say a recruiting company — may make thousands of dollars off of a single high-quality click, so they make for a better sponsor/advertiser.