First, sandboxing in Android isn't done at the Java level, it's done at the OS level, by running each app under a different UID and letting the kernel take care of enforcing what that UID is (and isn't) allowed to do. It's the same system that prevents different users on a "conventional" Linux system from accessing each other's private files. This is why Android apps can load and run native code (via JNI) without needing any special security permission or exemption. Native code is still in the sandbox.
Second, the real danger in this flaw isn't malicious apps tricking the user, it's malicious apps tricking other apps. Android's permissions system includes a feature called "signature-level permissions" which allows apps that are signed by the same publisher to grant each other permissions that aren't available to apps signed by other publishers. This bug means that a malicious app can pretend to be signed by Company X in order to gain signature-level permissions to interact with actual Company X apps in privileged ways. Depending on the app, this may allow access to sensitive data.