open("$ORIGIN/../lib/i386/jli/tls/i686/sse2/cmov/libz.so.1", O_RDONLY) = -1 ENOENT (No such file or directory)
The executable you're running looks for libraries in an rpath in addition to the normal library search path. The rpath here is $ORIGIN/../lib/i386/jli:$ORIGIN/../jre/lib/i386/jli. Normally $ORIGIN should be replaced by the location of the executable, here /usr/lib/jvm/java-6-openjdk/jre/bin.
Here, $ORIGIN isn't being replaced. The feature is turned off in executables running with extra privileges (setuid, setgid, or setpcap), because otherwise you might be able to inject a different library and so run arbitrary code with elevated privileges. (See this article for a more detailed explanation.) The security issue was discovered relatively recently; in Debian it was fixed in DSA-2122-1, so before you upgraded to libc6-2.7-18lenny6, your java executable would presumably have worked.
The symptom indicates that java is running with additional privileges. This is not the case in a normal Debian installation. Make sure that /usr/lib/jvm/java-6-openjdk/jre/bin/java is mode 755 and doesn't have any capabilities (getcap /usr/lib/jvm/java-6-openjdk/jre/bin/java, and setcap -r … to remove the capabilities if any).
(Original answer, which may be useful if you find that java works as root but not as other users, and it does turn out that you're invoking different binaries.)
My bet is that you have some other java version earlier on your PATH (sudo changes the PATH). Check what type java says — it's probably some different Java version for which ldd /path/to/bin/java reports libjli.so => not found.
And I speculate that the reason that this Java version can't find libjli.so is that it's looking for it through a rpath (library search path stored in the executable) that doesn't match the way it's installed. If you have the java binary in /some/where/bin/java, and it has a relative rpath (which is the way of the Sun JDK and OpenJDK), the library should be in /some/where/lib/i386/jli/libjli.so (assuming an i386 architecture). If the rpath is absolute, you need to either put libjli.so in the exact specified location, or set LD_LIBRARY_PATH to include where libjli.so is.
Add _JAVA_OPTIONS='-Dawt.useSystemAAFontSettings=on' to your /etc/environment file.
If you are running java applications from console, add export _JAVA_OPTIONS='-Dawt.useSystemAAFontSettings=on' to your .bashrc (if you run bash shell) or .zshrc (if you run Z shell).
Log out then log in again.
Best Answer
It appears to be an issue with the latest version of Java (7.u60_2.5.0-2).
If I rollback the versions of
jre7-openjdkandjre7-openjdk-headlessto 7.u55_2.4.7-1 using the pacman cachethen Java programs seem to work correctly again. Hopefully, Java or Arch Linux will post an update to fix this issue.