The NDK is the solution to all Android problems :)
I noted with interest that all the best performing games I have are all written in the NDK (get Addons Detector - used mainly for seeing which app contains those ** push advert APIs, but it also tells you which dev tools were used for an app).
Writing with the NDK means you won't have any worries about using the C++ library. If you want to keep your Java code, you can just use JNI to call it, or wrap it in a class.