There may be an easier way of doing it (in CS4), but you may select the arrowed paths, Object>Expand Appearance, and set Attributes>Overprint Fill/Stroke for heads and shafts.
Thank you very much Jacob, that’s solved the problem!
Jacobs way is probably the safest and most direct way.
However you should be able to select the stroke that the arrowheads are associated with and then set that to overprint.
The different seems to be that if you select the stroke on the canvas it does not select the effect as well if you select it in the appearance panel it select the stroke and any effect it contains.
I haven't tried it in this instance but that should work as log as the effect is contained with in the stroke. Even at this I would be more comfortable with the above technique
Instead of expanding the strokes, you can remove the overprint on the strokes and use the Multiply Blending Mode.
Good news, in CS5 since Arrow Heads are now assign directly in the Stroke panel, if you set your stroke to overprint, the entire path AND arrowed is overprinted.
You are welcome, Tosh.