I've downloaded from the Frostwire website and installed no problem, but when I try to run it I get:-

FrostWire version 4.17
Java version 1.6.0_0 from Sun Microsystems Inc.
Linux v. 2.6.27-7-generic on i386
Free/total memory: 63188112/72220672

java.lang.NoClassDefFoundError: Could not initialize class com.limegroup.gnutella.gui.GUIMediator
at com.limegroup.gnutella.bugs.LocalClientInfo.<init>(Unknown Source)
at com.limegroup.gnutella.gui.LocalClientInfoFactoryImpl.createLocalClientInfo(Unknown Source)
at com.limegroup.gnutella.bugs.FatalBugManager.handleFatalBug(Unknown Source)
at com.limegroup.gnutella.gui.GUILoader.load(Unknown Source)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:616)
at com.limegroup.gnutella.gui.Main.main(Unknown Source)
Caused by: java.lang.ExceptionInInitializerError
at com.limegroup.gnutella.gui.ResourceManager.setLocaleOptions(Unknown Source)
at com.limegroup.gnutella.gui.ResourceManager.resetLocaleOptions(Unknown Source)
at com.limegroup.gnutella.gui.ResourceManager.<clinit>(Unknown Source)
at com.limegroup.gnutella.gui.GUIMediator.getThemeImage(Unknown Source)
at com.limegroup.gnutella.gui.LimeJFrame.initialize(Unknown Source)
at com.limegroup.gnutella.gui.LimeJFrame.<init>(Unknown Source)
at com.limegroup.gnutella.gui.GUIMediator.<clinit>(Unknown Source)
at com.limegroup.gnutella.gui.Initializer.installResources(Unknown Source)
at com.limegroup.gnutella.gui.Initializer.initialize(Unknown Source)
... 6 more
Caused by: java.util.MissingResourceException: Resource bundle not found
at org.xnap.commons.i18n.I18nFactory.getI18n(Unknown Source)
at org.xnap.commons.i18n.I18nFactory.getI18n(Unknown Source)
at org.xnap.commons.i18n.I18nFactory.getI18n(Unknown Source)
at org.xnap.commons.i18n.I18nFactory.getI18n(Unknown Source)
at com.limegroup.gnutella.gui.I18n.<clinit>(Unknown Source)
... 15 more

STARTUP ERROR!

Any ideas would be appreciated. Gdebi installed Java which I already had, is it a version problem and if so why didn't it just use the version already installed?

I had some java programs that install went smooth, but the installer did not copy everything correctly. In the folder where the program was extracted, there were some library files that were not copied into the JRE folder. If there are some there, copy them to the /path to jre/lib/i386 folder. May have to check exact path. i386 is the folder you want, though.
Don't know if it will work for you. Hope it helps