Ah. I finally cracked it.
The solution is a little complicated. I got the gen here:
http://social.msdn.microsoft.com/Forums/en-US/vsto/thread/08f13e9d-895c-4102-b6d9-e327af8cf8c0
"First off copy the CLSID from the error window that appears in
VB.NET. Access the registry via Start, Run, Cmd, RegEdt32, enter. Once
the registry editor loads up, do a search (ctrl F3) on that specific
CLSID (I didn't include the braces, but it shouldn't matter). The
registry should find a key located under the HKEY_CLASSES_ROOT ->
CLSID subkey. Expand this key and you should see 3 nodes:
ProxyStubCLSID,ProxyStubCLSID32 and the important one - TypeLib.
Essentially what is happening is that when you make the COM call to a
specific Office assembly. The assembly opens up the registry and finds
this key which gives it the CLSID of the TypeLib it must call in order
to initiate a call to the COM.
Under the TypeLib key copy the (Default) Entry (It should be another
long CSLID key). Now the easiest way to find this new key entry
relating to the CLSID, is to go back up to the root key,
HKEY_CLASSES_ROOT and look for the TypeLib subkey. I did this by
simply pushing "T" on the keyboard till I got to the all the "T's" on
the level below the HKEY root. Once you find this key, highlight the
key and do a search (Ctrl F3) from this key for the TypeLib CLSID that
you copied earlier. Once you find it, expand it and see if there are
multiple versions of the typelib i.e. 8.3, 8.4, 8.5. You want to
eliminate the the later versions that are pointing to non-existant
TypeLib's."
I found here 8.3 and 8.4. Gingerly, I deleted the key 8.4, and it
worked.