VB6 based add-ins have a dependency on the Add-In Designer Object Library (msaddndr.dll), which is no longer shipped with Office 2013 (http://technet.microsoft.com/en-us/library/cc178954.aspx see under OSF section). If the add-in setup project did not include this DLL, then the Add-in registration would fail.

To resolve this issue :-

1. The add-in developer can include the msaddndr.dll file to the setup project, and redeploy the add-in. If VB6 Package and Deployment wizard was used, this can be done as shown here :- http://support.microsoft.com/kb/192136. And yes, this file can be redistributed.

Before deployment, make sure the VB6 developer machine has VB6 SP6 installed :-
http://www.microsoft.com/en-us/download/details.aspx?id=5721
and has the latest version of the msaddndr.dll from this cumulative update:-
http://support.microsoft.com/kb/957924

2. If there is no option for the setup project to be rebuilt to include this file, then this file can be copied from a machine which has earlier version of Office or VB6 installed and registered using regsvr32 command. You can then re-run the add-in setup. The msaddndr.dll file can usually be found at this location :-
C:\Program Files\Common Files\DESIGNER
or in case of 64 bit OS under
C:\Program Files (x86)\Common Files\DESIGNER

For the long term, if you are the developer of the add-in, please consider moving to newer supported ways of writing add-ins, such as Apps for Office or VSTO.

Update: A new KB article has been published about this issue :- A custom add-in that uses interfaces in the Msaddndr.dll file does not work in Office 2013