Eu mantive a mesma coisa usando o Ubuntu 16.04 e o 17.04. Alterar o ambiente de desktop não ajudou. Eu testei o Gnome3, gnome-flashback, mate ...
Eu posso reproduzir o problema com gnome-terminal, xterm e também gedit. Não consigo reproduzi-lo com o libre-office writer, firefox (linha de entrada de pesquisa do google).
O problema ocorre com muito mais frequência quando as teclas pressionadas são combinadas com o movimento simultâneo do cursor do mouse.
Corrigi o problema alterando o modo de aceleração do SNA para UXA:
Crie um arquivo /etc/X11/xorg.conf com o seguinte conteúdo:
Section "Device"
Identifier "Intel Graphics"
Driver "intel"
Option "AccelMethod" "uxa"
EndSection
Espero que ajude