Have you tried clearing the Move With Text option? I have had trouble with that when the header or footer includes graphics. Actually, I have had problems with it in a lot of situations. I created a macro to turn off the option, with a keystroke combination to run the macro.

I don't know the details of how your header and footer are set up, but sometimes, particularly if tables are involved, if the configuration permits you to use In Line With Text it may stablilize the position of the graphic.