From my observations the main reasons why people restrain from just beginning is the reward factor of modern foods. This is especially true for older people with an unsatisfactory life and no pleasure besides eating. Thus eating becomes the most important thing in ones life. Given the fact how sad, empty and stressful modern life is, it is clear why people eat to forget.
It's one of the things I can't get over since I switched from a highly rewarding diet to one which is almost non-rewarding. For the first few weeks and still now I feel the major factor in my life which makes life worth to live is gone. It is really depressive and difficult to overcome. Sounds ridiculous but it's true. The positive aspect is that I am forced to focus on meaningful activities which make me happy and endure the upcoming emotions which were buried by a higly rewarding diet.
A common answer when talking to people and recommend paleo (And I still recommend fruits, nuts, dried fruits, vegetables, starches besides meat and fish, so it is relative rewarding) is they can't do it because a peace of cake feels just so good.
It is important to understand the underlying mechanism here, which is unbelievably sad.
People are that addicted to neolithic foods, they virtually can't live without if they want to endure their state of existence.
They even admit it, but of course, they don't realize it's implications. Which is, life itself is that depressing that we need stimulating from processed sugary, fatty foods and opiates from milk and gluten, and coffee.
What surprises me is that even switching to whole foods is too much for a lot of people.
When going paleo, many people still use one or two things which are rewarding for them. Be it coffee, dairy (for some), really sweet fruits as a treat, chocolate and imitations of modern foods made of whole foods.
So it seems even going paleo doesn't automatically mean low reward, but for many it is apparently lower then before.
From my own experience I can only say, yes it is hard to switch at once. It feels like withdrawal.
Often I needed to treat me with a whole chocolate bar to endure everything.
When changing I think for most people it is helpful and possible to use rewarding food on a whole foods paleo diet. You can easily mix some fruits, nuts, dairy, sweetener, chocolate or other things together if you just need pleasure and still enjoy whole foods.
Another thing is that I am sure it can be really therapeutic to reduce reward, especially from food, to reeveluate your meaning of a great life and discover buried emotions you hide from yourself by eating a high rewarding diet or use other distracting modern things like tv, porn or too much internet consumption.
I can say for sure since I went lc paleo I feel like heaven if I eat fruit which I use as a treat like other people indulge in cakes, cookies or candies. One example how reduced reward increases sensitivity.