hi Robin,
i've with Tom on this, i know i can't eat anything wheat/bread, it makes me
feel awful for a couple days after.  as for dairy, i find i can do a bit of
butter or even yogurt, and still feel OK, but drinking a glass of milk would
give me killer belly cramps.  ditto for corn syrup, that ubiquitous high
fructose corn syrup that's in all kinds of junk food.  gives me badbad
cramps.
don't worry about calories.  when i first went paleo, i ate what semed to be
an ENORMOUS amount of food every day, but i still, much to my utter
amazement, having been brainwashed by the low-fat/low-calorie mindset, i
still lost weight.
and maybe you could switch to sweet potatoes/yams (sorry, i can't tell the
difference).  i love these things.  they're so sweet, having a baked yam is
like eating candy to me now.

JoAnn.