I found the issue. (Of course only after I posted to SO...)
The object was registering just fine. The issue was with missing dependencies in the constructor of the COM object.
Moving the initialization code out of the constructor and to an Initialize() method exposed the issue.
Visual Studio worked because of the directory it was running in.