Alt + F2: digite "xine" e tecle "enter".
Se funcionar, vc. pode editar o menu e colocar uma entrada para o xine que, na verdade, poderia ter sido instalado com o APT sem maiores problemas.
Fica, então, o conselho: quem quiser instalar algum programa, primeiro procure por ele no "adicionar/remover".