I've been taking 1000mg of magnesium per day to help with constipation. Constipation has been an on and off problem for my entire life, exacerbated by going paleo; before, I was eating basically a raw vegan diet consisting of a lot more roughage. Since the overall volume of my stools has decreased, I've become blocked up for as many as 5 days at a time.
Thanks to Paleohacks, I sought out a magnesium oxide supplement. It's been a small but sufficient help in this department. However, lately it seems like I have to take more and more to stay regular (regular for me means once per 2 or 3 days -- not great, but manageable). As I've dealt with constipation my whole life, with whatever fix, I'm wary of the dreaded word "dependency." With my understanding, magnesium draws water into your intestines, increasing the amount of stool and the ease of passing it. I suspect that with this unnatural supplementation, my colon may be getting used to the extra help and thus not working as hard in peristalsis. Am I just being paranoid? What's a safe upper limit to magnesium supplementation?
The amount of magnesium you take can be problematic in your health. I would suggest you stop taking it before it becomes toxic to your body. I had IBS-D for 10 years, started Paleo, got asymptomatic, but the first 1.5 months I switched to constipation instead. But over here at PaleoHacks someone made a wise remark: "diarrhea comes usually because you ate something you shouldn't have, and constipation because you didn't eat something you should have". This made sense to me, because bowel movements are driven by and large by the right gut flora. So I started a different regime:
I started taking two pills a day of multi-probiotics (iFlora)
I started drinking 1-2 cups of Yogi Kombusha Decaf (fermented tea)
I bought a yoghurt maker and I started making my own, probiotic, lactose-free goat yoghurt. As I write this, a new batch is fermenting for 20 hours now (to make it lactose-free).
I have no constipation anymore (neither diarrhea for that matter). I'm a regular once-a-day girl now, usually within 30 minutes of waking up.
I would echo the recommendation about improving your gut flora. Your elimination is basically stuff not being used by your body. Many folks have reported less content once going Paleo -- because they were eating less non-useable stuff. But if you are only going every few days with the help of Magnesium, it sounds like you don't have enough of the good bacteria in your gut.
Try a probiotic (you may have to experiment to find one that gives you what you are missing), eat fermented foods. You might want to read up on leaky gut syndrome or SIBO to see if any of that might apply to you. It sounds like your problem is higher up the chain. . .
Twenty years ago, I had a colon specialist who was a professor at a medical school operate on me for hemorrhoids. He told me most digestive disorders were the result of constipation. He told me if people had more fiber in their diet--he would have almost no patients. The modern diet just doesn't have enough fiber. There are two types of dietary fiber--soluble fiber and insoluble. In the palo diet most foods have both types of fiber. But if you must use a supplement use something like metamucil. The skins on apples, potatoes, etc will give u insoluble fiber. That coupled with milk of magnesia on the rare occasion you do get constipated will keep you regular. Also the old 8 glasses of water a day rule is TRUE.