I think you may have problems on Leopard if you have your default Java version set to 1.6. Try running /Applications/Utilities/Java/Java Preferences.app. Check the order of the Java application versions. I have J2SE 5.0 on top. If you don't, try moving it to the top (this should be the default). Then try running Arduino.
If that doesn't work, trying right-clicking on Arduino.app and select "Show Package Contents". Edit Contents/Info.plist (with TextEdit) and change the JVMVersion from 1.4+ to 1.5*