I tried pretty much all suggestions I could find scattered in various forums without luck.
The one thing that eventually worked for me (with Arduino 1.5.6-r2 Beta) was to replace the [arduino_root]/lib/jna.jar version (3.0.3 b2) that comes with the Arduino IDE with another version (3.2.7) that I had laying around from an installation of the Gradle build tool.
I will try to find out what version is shipped with Arduino and why theirs isn't working and update that answer then.