Samanthatouch, back before Google said link buying was bad, I was making good money on one site by selling links through a link broker company, which I think is what you're doing. Google announced this was bad, but I thought that was silly (people have been buying links before Google ever existed, and as long as they are useful to visitors, it makes sense to do), so I left them on. Immediately, my visible pagerank went to zero, but I couldn't see any ranking changes.
I changed the links to no-follow, switching services to a company that allows that, at a much reduced price.
It wasn't until I removed the links entirely that the domain recovered. That domain is the only one of mine that got hit by Penguin, despite having a clean backlink profile. It's had no paid links on it since 2008 or earlier, but it's possible that Google *assumed* some of my genuine editorial links were also paid because I had ever, back before they said it was bad, sold links.
I think it's possible that Google holds paid links against websites indefinitely, and when they are judging your site later, assumes the worst and punishes you accordingly.
If I'm right, which is a big if, and if things are the same now, which is another big if, you'd be better to keep your links do-follow and enjoy the money while it lasts, because there is no reprieve with Google. OTOH, I could be very, very wrong, so take this with a whole shaker of salt. ;)