I've seen the issue as resolved (at least twice), but it still occurs for me.
Despite having Java binary on slave and master, the SSH Slave plugin fails to find Java version.
Error log:
====================
[07/16/13 10:48:00] [SSH] Opening SSH connection to [...]:22.
[07/16/13 10:48:00] [SSH] Authentication successful.

[07/16/13 10:48:00] [SSH] The remote users environment is:
[07/16/13 10:48:00] [SSH] Checking java version of java
Couldn't figure out the Java version of java

[07/16/13 10:48:00] [SSH] Checking java version of /usr/bin/java
Couldn't figure out the Java version of /usr/bin/java

[07/16/13 10:48:00] [SSH] Checking java version of /usr/java/default/bin/java
Couldn't figure out the Java version of /usr/java/default/bin/java

[07/16/13 10:48:00] [SSH] Checking java version of /usr/java/latest/bin/java
Couldn't figure out the Java version of /usr/java/latest/bin/java

[07/16/13 10:48:00] [SSH] Checking java version of /usr/local/bin/java
Couldn't figure out the Java version of /usr/local/bin/java

[07/16/13 10:48:00] [SSH] Checking java version of /usr/local/java/bin/java
Couldn't figure out the Java version of /usr/local/java/bin/java

[07/16/13 10:48:00] [SSH] Checking java version of /bin/java
Couldn't figure out the Java version of /bin/java

hudson.util.IOException2: Could not find any known supported java version in [java, /usr/bin/java, /usr/java/default/bin/java, /usr/java/latest/bin/java, /usr/local/bin/java, /usr/local/java/bin/java, /bin/java], and we also failed to install JDK as a fallback
at hudson.plugins.sshslaves.SSHLauncher.resolveJava(SSHLauncher.java:557)
at hudson.plugins.sshslaves.SSHLauncher.launch(SSHLauncher.java:493)
at hudson.slaves.SlaveComputer$1.call(SlaveComputer.java:230)
at java.util.concurrent.FutureTask$Sync.innerRun(FutureTask.java:303)
at java.util.concurrent.FutureTask.run(FutureTask.java:138)
at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:886)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:908)
at java.lang.Thread.run(Thread.java:662)
Caused by: java.io.IOException: Failed to detect the environment for automatic JDK installation. Please report this to jenkinsci-users@googlegroups.com:
at hudson.plugins.sshslaves.SSHLauncher.attemptToInstallJDK(SSHLauncher.java:654)
at hudson.plugins.sshslaves.SSHLauncher.resolveJava(SSHLauncher.java:555)
... 7 more
[07/16/13 10:48:00] [SSH] Connection closed.