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.

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.