Anche io avevo lo stesso problema, ho provato a mettere la JVM che è un requisito richiesto, ma anche in queste condizioni non vuole andare. Quindi ho deciso di mettere AMSN che è uguale alla fine, è cmq un clone di MSN Messenger.
apt-get install amsn