Kevin,
A lot of people here are arguing the nuances of the diet.  Well, I'm far
from being quite that advanced (I'd love to someday, though), but my
lifestyle and tastes won't allow for that...yet.  Considering that you are
just starting the diet, you might want to make things more simple for
yourself so you don't get caught up in obsessing.

I've been on and off the diet more or less the last several months.  Each
time I get back on the wagon after being off, I do better and better.  So
falling off may be inevitable, but if you can keep your goals in mind and
not give up, it will be easier each and every time.  It has been for me.

I wouldn't obsess about flavorings for meat at this point.  Some purists may
claim that these little additives are what is making you fall off the wagon.
Well, for me, it seems easier to not worry if I add a bit of marinade here
and there and makes it easier for me to transition.  My main goal is to
avoid potatoes, rice, corn, and bread as side or main dishes, not worry
about the little bit that may be added to flavorings.  That said,
discovering paleo flavorings (using things like lemons, limes, fresh ginger,
garlic, onions, fresh herbs, etc.) can open up a new world for you, too.
But it takes time to figure all that out, and convenience sometimes wins
out.

Convenience is huge for me on determining whether I'll be "good" or "bad"
any particular week.  Hard boil some eggs so you always have some on hand
for a snack, keep some walnuts and almonds around (the purists can argue
about how they were heated and I'll just eat them for now,
thankyouverymuch), mix up some chicken and/or tuna salad (using regular or
homemade mayo, depending upon how purist you are--I don't obsess about
that--yet), and as I've mentioned before here, whenever I'm in a pinch for a
quick dinner, I make Paleo Hamburger Helper.  Brown hamburger, keep the
drippings in the pan, cut up whatever veggies you have around and sautee in
the drippings along with some herbs and spices to your taste, add the
hamburger back in and cover (I cover with several romaine lettuce leaves
rather than a pan cover) and simmer until cooked to your liking.  It's a
yummy easy meal that you can use as leftovers.  And I know that peanuts are
NOT paleo; however, when trying to get rid of carb cravings during my first
week or two, I find eating a spoonful of peanut butter can satisfy my
appetite for the time being.  I don't seem to react negatively, but that can
be an individual thing.  I figure eating a spoon full of peanut butter is
better than succumbing to my cereal cravings.

Like some others have said, it is a journey, and it will take you awhile to
completely switch.  You will have good and bad weeks. It does take awhile to
develop new habits and new cooking/preparation methods.  Don't worry too
much, but keep your goals in mind.
Michelle