Fixed. It seems there has to be some content in the body before you can add a footer and header to it, then you need to add a reference to them for each section like this:
foreach (var section in mainPart.Document.Body.Elements<WP.SectionProperties>())
{
section.PrependChild<WP.HeaderReference>(new WP.HeaderReference() { Id = mainPart.GetIdOfPart(headerPart) });
section.PrependChild<WP.FooterReference>(new WP.FooterReference() { Id = mainPart.GetIdOfPart(footerPart) });
}
Remember to add your header and footer last, so there is content in the document.
HUGE thanks to this answer: Add Header and Footer to an existing empty word document with OpenXML SDK 2.0