Depois de muitas horas, achei!
Abra o terminal e insira:
sudo gedit /etc/default/grub
Encontre a linha:
% bl0ck_qu0te%e altere para:
% bl0ck_qu0te%Em seguida, digite no terminal:
sudo update-grub
Isso também resolverá o problema do brilho da tela.
PS: Esta solução parou de funcionar depois de atualizar o sistema para o Kubuntu 13.04 (e provavelmente acontecerá a atualização para o Ubuntu 13.04 também). Mesmo configurando o grub de volta ao padrão, reinicializando, alterando-o novamente e reinicializando, o problema persiste.
Um detalhe simples fez a mágica, depois disso: vá para Configurações do sistema > Dispositivos de entrada > Teclado > Hardware > mudar o modelo do teclado para outra coisa > Aplicar > reboot > mudar o modelo de teclado para Generic | PC genérico de 101 teclas > Aplicar > reinicialize. Feito !!!