I would go back to Page Setup and rebuild that header—it is possible to get an invisible newline in there, as you can see from the following screen captures:
Can you tell which Page Setup image goes with which header? :-)
I don't have any idea what is going on with your footer, however. I assume when you say "right hand footer" you mean a footer that has the Show "Right" box selected, not something to do with odd/even pages, necessarily. Perhaps the cause would be more apparent if you would post a screenshot of the Page Setup box.