Interesting. Before I posted previously, I did a very quick test of the "align with page margins" and thought it was working. I read too quickly the settings on the page margin tab, forgetting that that was the vertical placement. Sorry about that.
I did some quick testing on one of my working spreadsheets just now and see your dilemma. If I play with the column width, sometimes I can make the page and header margins line up with the "align with page margin" box checked. It looks like the header margins are on too coarse a scale?