See:
https://support.microsoft.com/en-us/kb/2528942
I don't know if the FixIt there is the one you tried; if so and it fails, you may need to resort to the manual approach.
Do you have Office 2013 Service Pack 1 installed? If not, you should install that. Service Pack 1 resolves this issue for new files and will also prevent the problem from recurring with any files recovered with the Fix it solution in the above article.