I once had a similar problem after installing a newer version of Visio, but it was 'library not registered' instead of 'interface not registered' as you have now, but you never know the fix is the same. This was my fix then:

1. Open regedit and expand key HKEY_CLASSES_ROOT\TypeLib\{00021A98-0000-0000-C000-000000000046}.
2. You should only have one 4.? subfolder below it. Example on my PC:
   
3. If you have other 4.? folders which are empty, remove them.
4. Try to edit in Visio again from Cube. It should now work again.