This is a standard DLL Hell problem, it is caused by using the /codepage option for Regasm.exe. Or, more commonly, the Project > Properties > Build tab > "Register for COM interop" checkbox. Both do the same thing, they write the path to the DLL into the registry. It is a very good option to use when you are busy developing and testing the project, it avoids having to re-register the DLL into the GAC every single time you make a change.
But what it does not do is help the CLR find any dependencies. The normal probing rules remain in effect, it looks for an appname.exe.config file in the directory where the EXE is stored. And first looks in the GAC, next in the EXE path for dependencies. Configuration remains under control of the usual victim of DLL Hell, whomever has to maintain the EXE. Frequently the end-user. So, explicitly, it does not look in the directory where your [ComVisible] DLL is stored.
It is the mild kind of DLL Hell, just a plain file-not-found mishap. Much milder than the nasty kind, finding a file with the right name but the wrong version. In general a strong problem with Newtonsoft.Json.dll, there are about 35 versions in the wild. Having so many versions and it being such a popular library also begets the other kind of nastiness, the program using another COM server that also uses the DLL. But almost inevitably a different version. Tends to happen long after you declared your project finished. One of them is going to lose, 50-50 odds that it is you. 100% odds for the end-user.
Yes, the GAC solves this problem. Each library gets the version they ask for. Ideally Newtonsoft would solve this problem for you with an installer that deploys the DLL into the GAC. But it is not the kind of commitment that open source library writers ever want to provide. They want (and need) to make it your problem. Microsoft does this, but they also have Windows Update to ensure that critical bug and security fixes get deployed. And have a large number of people working on making sure that any new revisions are always backwards compatible with the original release so the version number doesn't have to change.
Do note that you can take advantage of Microsoft's commitment. You can also use the DataContractJsonSerializer and JavascriptSerializer classes to get this job done. Part of the framework, they rarely get it wrong.
Meanwhile, do keep mind that is just a file-not-found problem. You don't have to use the GAC on your dev machine, and it is better if you don't, it is just as easy to copy the file into the right place to keep the CLR happy. Which is the same directory as your VB6 test program. And, extra quirk with VB6, into C:\Program Files (x86)\Visual Studio\VB6 if you want to use the VB6 debugger. Do use the GAC when you deploy.