A megoldás:
apt-get install nscd
Noha nem tudom egészen pontosan, hogy mi okozza a jelenséget, de én is belefutottam már, és nálam az nscd (Name Service Cache Daemon) telepítése oldotta meg a problémát.
A munkahelyi gépemen Ubuntu 10.04 fut, nálam a gép tartományba léptetése után jött elő ez a probléma, de ahogy telepítettem az nscd-t, rögtön meg is oldódott.