I started to get this error after I had installed and uninstalled various MS SDKs
Error: Publish failed with the following error: Unable to cast COM object of type 'System.__ComObject' to interface type 'EnvDTE.Project'. This operation failed because the QueryInterface call on the COM component for the interface with IID '{866311E6-C887-4143-9833-645F5B93F6F1}' failed due to the following error: Error loading type library/DLL. (Exception from HRESULT: 0x80029C4A (TYPE_E_CANTLOADLIBRARY)).
Even reinstalling the SDKs didn't fix the problem.
I finally found the answer to the problem, which I'll post as an answer.
I opened 'cmd' with Administrator privileges, and did
cd C:\Program Files (x86)\Common Files\microsoft shared\MSEnv
regsvr32 dte80.olb
regsvr32 dte80a.olb
regsvr32 dte90.olb
regsvr32 dte90a.olb
and things magically worked after that.