Switching to a paleo/primal die gave me the worst IBS flares of my life.
I'm now eating more in line with The Perfect Health Diet, which is an ancestral diet that share similarities with primal, but is higher in starches. Vegetables are one of my IBS triggers, and when I stopped eating all those leafy greens and replaced them with low fiber things like potatoes and white rice, my digestive system was much happier.
I wrote pretty extensively about it, and what I did to heal myself here:
http://www.marksdailyapple.com/forum/thread62278.html