Well, the first-order solution is to not buy popup ads. Popup ads plus "software that 'cleans' your machine" equals "warning sign".
But presumably these ads work, and maybe they work so well that it's worth the collateral damage to one's brand from people whose first reaction is like mine. Hey, it's your life.
The other defense is to build the brand. Get some reviews from someone I've heard of. Name-check those reviews in the ad, maybe even with a link. Buy other ads in other places, where I might see them as I surf. Change the call-to-action buttons to read a little more like "learn more" and a little less like "install this thing now". Heck, I don't know.
And, yes, it's true, the existence of well-known trojans masquerading as "security" software is unfair to legitimate system-utility vendors, just as the existence of spam is unfair to legitimate friendly emailers and the existence of the flu is unfair to people who like to shake hands. What am I supposed to do about that? Encourage people to sneeze on me in the spirit of brotherly love?