I find that I have a similar, but opposite experience.  I can eat fatty meats and reach satiety at very appropriate calorie levels, but not on lean meats.

And my list of safe fruits is different than yours.  The one fresh fruit on which i have no control is bananas.  I also find that dried fruits are dangerous for me.  All perfectly paleo.

So yes, there are a few paleo foods to which I may have intolerance/addictions.  But just about EVERY non-paleo food is that way for me.

it is also one of the reasons that I look on coffee skeptically, no, i know it's not a legume, but yes it does require fire, Ray certainly didn't consider it paleo.
Bottom line?......it's damn hard for most people to give up.  That's the red flag of addiction, IMHO, and reason enough to suspect and intolerance.

It's not just the caffeine, either, although that is very addictive, because apparently it's just as hard to give up decaf.

Kathleen