I didn't — I thought I mentioned that. I had intended to provide one as soon as I had a chance to, but it turns out that Eshel encountered the same issue and provided a recipe (thank you, Eshel). The only difference in my case is that face-remap-set-base is used, rather than face-remap-add-relative.
As far as I can tell, this same bug occurs in the mode-line as well as the header-line. I.e., there was an existing bug in the mode-line and it was replicated to the header-line after the two new faces were added.
Thanks,
Aaron