Você deve ver a saída do seu programa em ~/.xsession-errors
. Se você quer rodar o comando em um terminal em si, você precisa instalar um terminal que permita especificar o comando a ser executado (a maioria deve suportá-lo), isto é, para o xterm você pode executar:
xterm -e python /path/to/script
e coloque-o no seu arquivo de início automático.