If Google can associate these links with a company that's brokering paid links, it can cause problems for you whether it's "no follow" or not. I just got an email from this company and am finding lots of posts like this referencing them so expect they'd be on Google's radar. I'm always looking for good guest posts and have worked with agencies promoting their clients when the content is good and relevant, but not any brokering paid links.