Newspapers have a huge amount of unrealized value. They are probably one of the most trusted sources of relevant local content available, even today. But if newspapers maintain business as usual and don't fully leverage this advantage, this power will continue to slowly erode with ocassional landslides when revolutionary tech companies emerge.
But I'm not here to bash newspaper, we're here to talk about how to fix it.
One of the hardest things about getting any business up and running is getting early users and visibility. Newspapers by default have the distribution platform built in. My recommendation is that newspapers move away (not completely) from relying exclusively on classified to make others money. And use their INCREDIBLY VALUABLE distribution platform to promote locally relevant services which they have equity in.
Andrew Mason from Groupon stated that the only real competition he'd really have is from newspapers or local radio stations. And he's right. But I haven't seen newspaper really doing this. (I believe Boston Globe did a deal with BuyWithMe but I haven't been in boston in a while).
The failure to really innovate on approaches like this is partly a function of the expertise of people who work for newspapers. You've got reporters, who know their city inside out, ad managers that know the local businesses and sell ad space, web devs who do layout for stories and awesome infographics, but you don't really have a "product development" team. Folks who's responsibility it is to create marketable products FOR the newspaper. I guess this is where you come in, but from your post, it looks like this is a side project for you.
I've thought about this some, and really think this is the way forward for them. There needs to be a big structural change in how revenue is generated and how the business is run. Classified alone won't cut it.
I've got one largely developed project and several early stage plans that I think would work well with a newspaper partnership, so if you'd like to talk, drop me a note (email in profile).