So I have a C# object which exposes a COM interface through interop, and it was working. Then I did something, and when I went to reload it, it said the component was not registered. I confirmed that the ProgID was in the registry, and everything appeared to be good.
... It turns out that if the constructor for an object which is being constructed for a COM object instantiation throws an exception, the CoCreateInstance call will return that the component is not registered. This is not normally a problem with native C++ COM objects, since they run the constructor code as part of the registration process, so you'd catch the error earlier. However, C# COM object apparently do not, and the error coming from COM is very misleading.
Just an interesting tidbit for COM interop.