Well that's odd, I'm running java-1.7.0-openjdk-1.7.0.9-2.3.7.0.fc18.i686
Which is supposedly the latest Java 1.7 (Available in Fedora 18). I downloaded Spine prior to posting this post, from my super secret URL.
In any case, I did try to run the JRE bundled in Spine, (via Spine.sh). It won't run. (Same error).
[Nushio@Serenity spine]$ sh Spine.sh
Error: Could not find or load main class com.esotericsoftware.spine.editor.launcher.Launcher
Edit: Here's a comparison of Java versions. afaict, Fedora's Java is slightly newer.
[Nushio@Serenity bin]$ ./spinejava -version
openjdk version "1.7.0-u6-unofficial"
OpenJDK Runtime Environment (build 1.7.0-u6-unofficial-b24)
OpenJDK Server VM (build 23.2-b09, mixed mode)
[Nushio@Serenity bin]$ java -version
java version "1.7.0_09-icedtea"
OpenJDK Runtime Environment (fedora-2.3.7.0.fc18-i386)
OpenJDK Server VM (build 23.7-b01, mixed mode)