Well, if Java means Swing, you are extrapolating from a
very bad example. For instance, the Qt library looks pretty native on most platforms, and with some platform-specific code (e.g. proper support for application menus for OS X) Qt programs can also feel native.
I wrote some small Qt GUI applications (mostly frontends to scientific tools), and most people don't notice it's not native.
Also, this depends a bit on your market. Some markets are more sensitive to nativeness than others, for instance, by operating system:
OS X > Windows > Linux/UNIX
In OS X people are quite used to polished native applications that conform to Apple's HIG, they will also expect it. Windows is somewhere in the middle, there are some widely used applications that do not look native. Linux/UNIX users seem to be completely oblivious to nativeness, since they are used to having a mix of Qt/Gtk+/Tk/Lesstif/whatever applications.