How did you install it?
For me alt-f2 -> "phex" works (in Gentoo with KDE). But that's cheating, since it's in effect a commandline, too
If you use the svn version, just click the file "build-and-run" (you might have to make it executable before that). It first builds Phex from sources and starts it afterwards.
You can also create a file in the downloaded folder containing the lines:
---begin file---
#!/bin/sh
cd lib && java -ea -Xmx128m -jar phex.jar
---end file---
Make it executable (chmod +x <filename>) and click it.
I hope this helps you!