A maneira do X11 é colar com o clique do meio, que pode ser simulado clicando nos botões esquerdo e direito do mouse simultaneamente.
Se você precisar de colar com o botão direito do mouse, sacrificará outra funcionalidade (clique com o botão direito do mouse) ou precisará corrigir o gnome-terminal.
Mapeie novamente o clique com o botão direito para agir como um clique do meio
Use o xmodmap para desativar o botão do meio e mapeie novamente o botão direito para agir como intermediário. Isso afetará todos os aplicativos X, por isso não parece desejável. Para ver temporariamente se esse é o comportamento desejado, execute este comando:
xmodmap -e 'pointer = 1 0 2'
Se você preferir trocar os botões do meio e do botão direito, tente o seguinte:
xmodmap -e 'pointer = 1 3 2'
Reconstrua o gnome-terminal com um patch para permitir a colagem do clique do meio
Instruções para isso no gnome-terminal 2.32 (Ubuntu 11.04) estão disponíveis aqui: link
A versão atual do gnome-terminal é 3.6 (Ubuntu 14.04). Escrever e aplicar um bom patch é um procedimento muito avançado. Eu recomendo que você tente aprender a usar o meio-termo ou a esquerda e a direita "mouse chording", e se eles não satisfizerem você, então troque seus botões direito e do meio do mouse usando xmodmap. Se você realmente quer experimentar o patch, deixe um comentário, e eu vou trabalhar com você.