Eu acho que o problema é que gnome-terminal
começa com #!/bin/python
e no seu caso essa referência a nada
Por favor, tente sudo dpkg-reconfigure python
e leia este A segunda resposta desta questão
E bem-vindo ao mundo GRATUITO do GNU / Linux
Ele deveria ser um comentário, mas eu não tenho reputação suficiente: P