Вполне возможно, что из-за ClassLoader-ов, ведь это проявляется даже без JNI. В Java-коде такой класс тоже не будет найден, пока не будет явно указан ClassLoader (Class.forName(«package.Class», true, myLoader)).
Если я не ошибаюсь, то System.loadLibrary() загружает либу в контексте того класслоадера, который загрузил класс, вызывавший эту функцию. Так что вполне возможно, ваша J-либа и ваш основной код были загружены из разных класслоадеров, и System.loadLibrary был вызван из класслоадера с кодом — тогда библиотека не найдет JNI-методы, а JNI — не найдет библиотеку.
