There are some explanations for installing protege (with JDK 6 or later). But I ran into an additional problem when I tried to start the OntoGraf plugin.
If protege starts without problems (rename felix.jar or just use JDK 6 and not the latest version) but the OntoGraf plugin gives an error just install graphviz. On Linux Mint 12 you can run:sudo apt-get install graphviz
Now the plugin works without further problems.