Your dog may also have a problem with yeast. Try some something like
http://www.biokplus.com/ which has a high live culture content. We've been using the Orijen 6-fish quite happily since it came on the market. Poops are a little softer than usual but other than that, I've been very happy with my dog's improved overall health.