(Movido a resposta de maio de 2012 da pergunta para aqui)
Então agora eu “consertei” isso reinstalando o sistema. Não faço ideia do problema.
Para acertar o teclado em qualquer lugar (tty, tela de login do KDM, KDE) eu tive que correr
dpkg-reconfigure locales # Kept only (de_CH|en_US|ru_RU).UTF-8
# Selected de_CH.UTF-8 as default
dpkg-reconfigure console-data # Selected German (Switzerland)
dpkg-reconfigure keyboard-configuration
# Selected my 105-key Cherry CyMotion Xpert
# AltGr on right Alt, no Compose key
A execução da configuração do teclado não funciona, pois essas configurações são específicas do teclado padrão selecionado em locales; para en_ *, por exemplo não há AltGr nem chave de composição.
(sistema baseado em Debian.)