No meu Ubuntu 14.04, tudo que você precisa fazer é, como acima, clicar com o botão direito do mouse, abrir com outro aplicativo ..., e apenas selecionar o programa. Se o programa não estiver listado, pressione o botão "Mostrar outros aplicativos" e escolha a partir dele.