You can try to bundle the app specifically for mac users (xcode should do all the nitty gritty work for you although from memory it wasn't that trivial). Never directly had the problem you describe so this may or may not work. Bundling apps is the normal app-type distribution for mac users, and depending upon your client base may prefer this sort of distribution. See:
Bringing your Java Application to Mac OS X
and
Bringing your Java Application to Mac OS X
You may also wish - if you app does not require 1.6 - to compile for 1.5 since older macs that run leopard and below by default do not have 1.6 installed.