Ok, descobri qual era o problema.
Está faltando uma entrada no arquivo. Coloque a seguinte entrada no arquivo
Type=Application
Depois de salvar o arquivo, você notará que ele é alterado para parecer mais com um aplicativo do que com o que parece agora (um arquivo de texto / script).
Mesmo se você tornar o arquivo executável, o Ubuntu Desktop não saberá se esse arquivo é um script ou aplicativo e assume que é um script. Mas se você colocar o Type = Application, ele será executado corretamente.