You don't quite provide enough information to answer with certainty, but there are enough hints to guess at what you are doing.
When your client app asks for the COM object, the .NET runtime is invoked and it locates the COM-exposing assembly DLL from the information stored by RegAsm (specifically by the /codebase parameter). But after that, it's all .NET assembly loading rules - including the loading of dependencies.
If your COM assembly has dependencies, the dependent assemblies must be locatable from the client process. It doesn't matter whether the dependencies are in the same folder as the COM DLL - the one loading those dependencies is the process, not your COM DLL. The .NET runtime uses a process called Fusion to decide where to look for .NET assemblies.
You have two practical choices:
Put the COM DLL, its dependencies and the client EXE all in the same folder. This works if there is only one client, and you control the client (so, don't do this if the client is IIS, for example). It's the simplest solution.
Give all the .NET components a strong name and deploy them to the GAC1. You still have to run RegAsm; but don't use the /codebase argument.
It is also possible to customize the Fusion rules by giving the client app a manifest with the proper entries, but that's too much of a hassle. The other options are more practical.
If this doesn't describe your problem, then I would use a combination of SysInternals' (now Microsoft's) Process Monitor and the .NET fusion log functionality to look into where the process is seeking the different DLLs.
1Technically you don't have to put the main COM DLL in the GAC, but it makes no sense to use /codebase for the COM DLL when you have to deal with GAC anyway. At that point you might as well put them all in the GAC