**New Answer:** Take a 2-bridge knot, and perform hyperbolic
Dehn filling (so that the core of the Dehn filling is geodesic),
and so that the filling slope has intersection number $>1$ with
the meridian. Then the meridian will not be primitive, since it
will be a multiple of the core of the Dehn filling. 2-bridge
knots have a genus two Heegaard splitting, which has a spine
for the handlebody which is a wedge of two meridians
at the bottom. This remains a spine in the
Dehn filling, so the loops represented by the meridians are not
primitive. This also works for the (2,n) torus knots (which are
2-bridge), so I think Charlie's answer is right (at least for
many small Seifert fibered-spaces).

**Old (non)Answer:**
Here's almost an example. All punctured torus bundles have
Heegaard genus $\leq 3$, and many have Heegaard genus 3 (I discussed
this once in my defunct blog). One may find a genus 3 Heegaard splitting
of any once punctured torus bundle by taking two copies of a
fiber, tubing them together along the boundary on one side,
and adding a handle to the other side (drill out discs from
both fibers, and glue an annulus in). By a theorem of
Moriah-Rubinstein, most Dehn fillings will also have
Heegaard genus 3 if the punctured torus bundle does.

The Heegaard splitting of the punctured torus bundle
has one side which is a handlebody,
and the other side a compression body. We may think of the
handlebody as a product neighborhood of the fiber (which is
a punctured torus) with a 1-handle attached. We may find a
spine for the handlebody which consists of a wedge of two
loops which is a spine for the punctured torus, together with
another loop going through the 1-handle.

Now, the peripheral curve of the punctured torus is not primitive
in Dehn fillings along curves which intersect the longitude
multiple times. This curve is represented in the spine not
as an embedded curve, but has multiplicity two (since it is
a commutator of the generators). If we choose a small punctured torus bundle
of genus three, most Dehn fillings will be small (non-Haken) of
Heegaard genus 3, and so this Heegaard surface will be strongly
irreducible. But the peripheral curve will not be primitive,
since it will be a multiple of the core of the Dehn filling. However,
it is not embedded in the spine.

Even though this doesn't answer the question, it gives a strategy
for trying to find an example. Namely, if one can find a 1-cusped
hyperbolic 3-manifold which is small, and contains an incompressible
surface with boundary, such that the boundary slope is a generator in
the surface,
and such that a tubular neighborhood of the surface (or a slight modification by
drilling a hole in a tubular neighborhood)
is a minimal genus Heegaard splitting, then many Dehn fillings will
have the desired property.