There are inherent problems which are not Java specific. Your app would need to have very few rights for starters, the sandbox should be as small as possible (like browser/JS).
If you have different permissions and a complex sandbox with a runtime that supports classloaders, you run into the same security problems that Java currently enjoys for applets.
Security, permission management, and sandboxing would be critical concepts of a system running code from potentially untrusted sources. But I don't think the security problems often associated with Java and Flash are inherent for such sandboxes. Web browsers themselves are an excellent example of sandboxing that seems to have stood fairly well against attacks. And NaCl demonstrates that the security model of web browsers is extensible to native code.
If you have different permissions and a complex sandbox with a runtime that supports classloaders, you run into the same security problems that Java currently enjoys for applets.