>1.  Will my traveling make things extra difficult?

maybe, but there is usually always a restaurant where one can order a steak
and a salad.  or bacon and eggs.  a lot of paleo food is quite portable:
pemmican, dried fruit and nuts.

>2.  Is it easier to make the change gradually or to switch cold turkey?

just jump right in.  you'll appreciate the positive changes more.

>3.  Are vitamin supplements necessary?  Is it OK if I take them for peace of
>mind?

 i take a small handful every morning, based on the assumption that the food
i eat is in no way comparable, nutritionally, to what our paleo ancestors
had access to.

>4.  Starchy fruits and vegetables?  Where can I get a more extensive list of
>such things to avoid?

i'd say zucchini or summer squash is OK, but not the winter squash (like
pumpkins).  the only starchy fruit i can think of is a banana, and that's paleo.

>5.  Should I expect any weird side effects?

sure.  your weight will stabilize, you'll sleep like a rock, and any
complexion problems should clear right up.  also, not from personal
experience, but from what i've read on this list, your eyesight may improve
and insects will avoid you ;)

JoAnn.