I haven't experienced this myself, but a user on SEO Chat seems to feel that the only way to get links is to pay for them. Here's the relevant thread.
The quote in the OP that got me thinking was: "I am trying to get some good quality links. I don't want to waste time with spammy directories etc.... But every company i have spoken to all want payment for a link...Are the days when you could get a link for simply writing content or providing info gone? Do you always have to pay for quality links?"
Also interesting - some people in that thread suggest that paid links are not necessarily a bad thing if done in moderation. Do you agree with that? How do you structure your backlink profile and balance short vs long term risk?