I am the very same....I have no trouble sticking to Neanderthin  except for
the cheese and minimal butter use.  I'm feeling great and seem  to have no
symptoms from cheese (I abstain from milk & other dairy though)  and very little
butter.   I used to have abdominal pain and bloating  on my previous SAD (std
Amer. diet).  Now it has been 6 months with no  flour, sugar or grains and no
pain or bloating.  Not too sure I could stick  with paleo without my beloved
brie or cheddar with my eggs and paleo  bacon.  I think I may try a trial of
abstaining from cheese and see if I  can do it for a week and see if I notice any
difference.
Lisa