Muito estranho isso. Qual versão do KDE você está usando? Esse problema pode ser algum bug dessa versão que você está usando. Já experimentei na versão 4.4.x e 4.5.x e consigo mudar o tema do KDM sem problemas.
Tente carregar o "systemsettings" no modo administrador. Talvez você consiga mudar esse tema.
Tecle ALT+F2; digite: kdesu systemsettings; ENTER
Depois entra na opção para mudar o tema do KDM e teste.