Korábban nekem is voltak hasonló gondjaim (pl. nagy Í-t nem tudtam beírni, Num Lock nem működött), 1.6.0-3ubuntu4.1 verzióval gond nélkül megy minden (Ubuntu Natty fut a gépemen).
Itt letöltheted ezt a verziót:
http://packages.ubuntu.com/natty/rdesktop
Próbáld meg telepíteni, ha függőségi gondok miatt nem települ, akkor csak bontsd ki a csomagból a keymap-et és másold be a meglévő fájl helyére. Hátha segít.