My code starts in Java, invokes C++, which then invokes Java back again for things like finding, getting, and setting field values.
In case someone looking for a C++ approach finds this page, I'll plough on with this:
What I'm now doing is wrapping my JNI method bodies up with a C++ try/catch block,
JNIEXPORT void JNICALL Java_com_pany_jni_JNIClass_something(JNIEnv* env, jobject self)
{
    try
    {
        ... do JNI stuff
        // return something; if not void.
    }
    catch (PendingException e) // (Should be &e perhaps?)
    {
        /* any necessary clean-up */
    }
}
where PendingException is declared trivially:
class PendingException {};
and I'm invoking the following method after invoking any JNI from C++, so if the Java exception status indicates an error, I'll bail immediately and let the normal Java exception handling add the (Native method) line to the stack trace, while giving the C++ the opportunity to clean up while unwinding:
PendingException PENDING_JNI_EXCEPTION;
void throwIfPendingException(JNIEnv* env)
{
    if (env->ExceptionCheck()) {
        throw PENDING_JNI_EXCEPTION;
    }
}
My Java stack trace looks like this for a failed env->GetFieldId() call:
java.lang.NoSuchFieldError: no field with name='opaque' signature='J' in class Lcom/pany/jni/JniClass;
  at com.pany.jni.JniClass.construct(Native Method)
  at com.pany.jni.JniClass.doThing(JniClass.java:169)
  at com.pany.jni.JniClass.access$1(JniClass.java:151)
  at com.pany.jni.JniClass$2.onClick(JniClass.java:129)
  at android.view.View.performClick(View.java:4084)
and pretty similar if I call up to a Java method that throws:
 java.lang.RuntimeException: YouSuck
  at com.pany.jni.JniClass.fail(JniClass.java:35)
  at com.pany.jni.JniClass.getVersion(Native Method)
  at com.pany.jni.JniClass.doThing(JniClass.java:172)
I can't talk to wrapping the Java exception within another Java exception from within C++, which I think is part of your question - I've not found the need to do that - but if I did, I'd either do it with a Java-level wrapper around the native methods, or just extend my exception-throwing methods to take a jthrowable and replace the env->ThrowNew() call with something ugly: it's unfortunate Sun didn't provide a version of ThrowNew that took a jthrowable.
void impendNewJniException(JNIEnv* env, const char *classNameNotSignature, const char *message)
{
    jclass jClass = env->FindClass(classNameNotSignature);
    throwIfPendingException(env);
    env->ThrowNew(jClass, message);
}
void throwNewJniException(JNIEnv* env, const char* classNameNotSignature, const char* message)
{
    impendNewJniException(env, classNameNotSignature, message);
    throwIfPendingException(env);
}
I wouldn't consider caching (exception) class constructor references because exceptions aren't supposed to be a usual control flow mechanism, so it shouldn't matter if they're slow. I imagine look-up isn't terribly slow anyway, since Java presumably does its own caching for that sort of thing.