At the same time there are a few primal eaters I know (not many) that have the same issues. One of them has been primal since before it was more well known and he still has the same problems he had before switching. He'd originally thought that it was because he was "bad" by eating a certain bread he liked on occasion and so cut out all grains completely without any further results.
Oh, and I keep trying to find some more solid info between the paleo and primal. I did a search on the blog here and found a few things...but other places online give different views on what the difference is.