I had this exact same problem. Here’s how I fixed it:
Go to
HKEY_CLASSES_ROOT\TypeLib\ and search for Office.Interop.Excel.
I found HKEY_CLASSES_ROOT\TypeLib\(guid)\1.8 but its child nodes were empty! I deleted it because Office 15 wasn’t installed on that machine, and hey presto – it worked.
Either our VSTO project installer, or our own custom installer must have placed the 1.8 folder there.
I found the solution here:
Error accessing COM components