Solved this. It turns out that that my installer program was detecting if Windows was 64-bit or 32-bit and registering the DLL appropriately. It turns out that the person having the problem was running 64-bit Windows, but 32-bit Excel. So when the DLL was called from 32-bit Excel, it thought it wasn't registered.
The fix was very simple and proven out by testing on the target system: I just told my installer that if it detects 64-bit Windows to register the DLL using RegAsm for both 64 and 32-bit.