Don't know how much help my info will be, but you might find nuggets in it that will be useful to you.
My mom takes two probiotics after several years of having to take antibiotics for chronic urinary tract infections. I had tried her on several types of just acidophilus with no visible benefits. When I switched her to Florell probiotic, her BMs were more regular and normal looking. Another round of antibiotics changed that and so I tried Culturelle which tends to cause diarrhea if she takes it at the recommended dose. Now I switch off, Florell one day, Culturelle the next, and that seems to work pretty well for her. From the little bit of research that I've done (and it is only a LITTLE), I am starting to think that probiotics, and gut bacteria in general, are very personalized (although I think I read that family members have very similar gut bacteria makeups). You may end up having to try different things until you find what works for you. But that is IMO. Personally, I would try what people recommend and have had success with, but if one particular brand doesn't work for you, try another. The few articles I've read about gut bacteria in Discover magazine have me thinking that the balance is very important but it's not something that medicine has focused on until recently.
As for cutting out sugar--I have a big problem with Candida Albicans (yeast) throughout my body. When you have a yeast imbalance, the toxins they release as they die can cause all sorts of issues. To keep it in check, I have to watch my sugar and caffeine intake (which I'm not always good about). When I first started doing that, I went too far the other direction with cutting out sugar. So, again, I would recommend working towards a balance.