Having rolled out office 2013, I thought it was plain sailing until I received some documents from a customer and could not open them. I kept getting this error message.
Some research led me to this excellent MS article.
http://support.microsoft.com/kb/2749199
Worked a treat for me. In my case, I added the root location where I keep my documents as Trusted location.
Hope this helps.