I came to paleo sorta by accident from the wheatless
celiac.  My background is PA Dutch on the maternal side
where a table isn't properly set for a meal unless it
includes SEVEN sweets and SEVEN sours!  My dad was a meat
'n' potatoes for all meals man who thought green leafys were
great for grazing animals.  Plus I am a child of the typical
American culture and was taught to invest a lot of emotion
into my food.  I suspect your parents are either very like
me or either of my parents or a combination of us.

Here's what I would suggest:  Find out exactly what diet
they are being given.  No doubt it will be the typical
"diabetic" or "weightloss" diet that restricts everything
:)  A few weeks more or less of this diet isn't going to do
any more harm than they have already got going on, so spend
some time seeing how they do with it.  LISTEN to what they
say, especially their complaints.  Don't try to teach now;
simply establish rapport.  Now, take the things they are
griping about most and try to come up with something close
that is also nearly paleo.  Make up the food yourself and
take it as a gift.  Do they miss ice cream?  Make them some
frozen fruit smoothie.  That kind of thing.  Just remember
that these folk are like the rest of us were - ADDICTED to
the foods that are hurting them.  One of my all time
favorite comfort meals used to be chicken fried steak,
mashed pots with lots of cream gravy and corn, followed by a
hefty piece of chocolate pie.  Now that meal might still
fill the emotional need but I know from experience that it
will make me quite ill :)  So now when I feel the need of a
comfort meal I make a chicken stirfry with a bit of orange
juice and cider vinegar added at the last minute for a
sweet/sour tang.  The only reason I was able to make such a
great change was because I discovered I really really liked
my new chicken dish.  They aren't going to easily give up
the things they like for things they don't.

And if they're not following their dietary advice at all,
you can still teach by example.  Just make up a meal of
something really yummy and paleo and treat them.  Just don't
try to start with anything real exotic or vastly different
from the foods they are used to eating.  If it is too
different, they will be automatically set to resist it.

Best of luck to you and them!
--
   Elisi Tsayonah, AniWodi, ghigau,
   St Francis River Band of Cherokee