Rather than penalize, Google sometimes does just ignore paid links for the purposes of PR and link juice. I've seen this in paid online ads from local and regional newspapers websites. These publishers are just big enough (and clearly not trying to evade anything - they just don't know) that I guess Google is willing to accept the trade-off.
Nonetheless, Google has been very clear that they want paid links to be nofollow - or else the publishers risks a penalty. A minor penalty can be a demotion of toolbar PR that doesn't really affect ranking. However, if they want to in any given situation, Google will totally wipe out rankings for a site that sells dofollow links. So there is a gradient approach on how this guideline violation is handled.
Nevertheless, I would not advise any site to sell dofollow links. If you can't drive actual traffic to your advertiser (or at least offer them good impressions) don't sell PR - it can kill you.
In fact, this particular warning that the OP is communicating sounds very much like it could be a paid link issue. However, the poor targeting of Adsense also sounds suspicious and very worth looking into. There could well be a big technical problem.