Isto pode ser porque quando você executa o gnome-terminal do gnome-terminal, todas as bibliotecas e outros códigos necessários para executar o programa já estão na memória. Se o programa do terminal ainda não estiver em execução, as bibliotecas deverão ser buscadas no disco - o que pode levar algum tempo. A lentidão ocorre se você iniciar uma nova instância do programa terminal a partir do ícone quando você já tiver outra instância em execução?