Desculpe... duas furadas no mesmo tópico.
O xmodmap não resolve apenas no terminal não; ele é ativado pelo terminal, mas vale pra toda sua sessão gráfica. Eu costumo muito usar isso quando faço acessos remotos via FreeNX, sempre acaba com essa mesma tecla desconfigurada.
Sabe o que me deixa mais cabreiro? Vc disse que notou o problema quando a máquina voltou do conserto. Mas como poderia ser algo de software? Só se o técnico tivesse mexido em alguma coisa, certo? Mas, cara, é uma máquina Linux... por mais que ele soubesse mexer em linux, ele não teria acesso, certo? Eu ainda acho que seria mais algo relacionado ao hardware mesmo.
Uma forma de verificar isso seria você bootar a máquina com um LiveCD, e ver o comportamento do teclado. Se voltar ao normal, é software; se continuar com problema, é hardware, e vc deveria levar a máquina novamente ao conserto e pedir pra verificar.