I've seen a few reports lately of people having issues when they set the "register output" property on their project to "Yes". Here's my quick debugging guide for solving this problem.  

Are you deploying all your dependent libraries? Check out depends.exe to see what you are dependent on (ignore msjava.dll, that's not a real dependency), and make sure they are all on the device and locatable (i.e. in the \Windows or application directories) by your app.

If they are all present, then the next step is debugging your registration calls.

• Switch the register output property on the deployment property page to false.
• Create a Win32 project (select the "Application" project type), and replace the code in WinMain with simple code to have it load your library (LoadLibrary) and call DllRegisterServer (if you made this app take an argument that was the name of the dll, you'd basically have regsvrce.exe).
• Set this application to be the startup project in the solution.
• Set a breakpoint in your implementation of DllRegisterServer, and figure out what is causing this error (notice how I helpfully skipped any helpful hints on this :) ). You can also set a breakpoint in DllMain to see what's happening when the library gets loaded if the call to LoadLibrary fails.
• Fix the issue with the registration code. (Again, I'll helpfully skip anything useful here).
• Reset the register output property on the deployment page to true. Remove the Win32 project from your solution.

Hopefully this helps some of you out there. Cheers!