Visual Studio 2008 Publish fails, can't load dll (envdte.dll)

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.