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.