I think this depends on the java code's implementation. If it proves not to thread, here's a potentially cleaner alternative to messy JNI:
Create a Java daemon process that communicates with your store, which INTERNALLY is threaded on requests, to guarantee efficient load handling. Use a single ExecutorService created by java.util.concurrent.Executors to service a work queue of store/retrieve operations. Each store/retrieve method call submits a Callable to the work queue and waits for it to be run. The ExecutorService will automagically queue and multithread the store/retrieval operations. This whole thing should be less than 100 lines of code, aside from communications with the C program.
You can communicate with this Java daemon from C using inter-process communication techniques (probably a socket), which would avoid JNI and let one Java daemon thread service numerous instances of the C program.
Alternately, you could use JNI to call the basic store/retrieve operations on your daemon. Same as currently, except the java daemon can decorate methods to provide caching, synchronization, and all sorts of fancy goodies associated with threading.