Adding the three properties suggested above has worked for me in the past, but it didn't work this time, when I had a Column Group in my Header.
I added a parent Group to my first column and repeated the headers per Group. It worked, but wasn't exactly the layout I was looking for.
Then I researched how come it works when you use the wizard and not when you add the item manually. Interestingly enough I have an identical report in which case the Header also has a Column Group and headers DO repeat. So I figured I wasn't doing something right.... I compared both XMLs and found the following properties:
These are the properties controlled via the Tablix Properties panel.
If I add <RepeatRowHeaders> to my bad report's XML, SSRS deletes it. It won't let me add the property. However, you I tried adding both directly onto the XML and it worked.
So also try that.