1. More memory decreases the chance the message occurs.
2. The problem seems to be related to the availability of a network, but only just after boot up. After that, network seems irrelevant
3. The problem seems to be connected to whether a cd is in the tray when kdm starts or not.
4. Loading a desktop picture or not, seems to have connection to the problem as well.
So, it seems safe to deduct that the default order of starting things in kdm start is not quite right. Obviously, more RAM causes some processes to start - and finish - faster. A disk being present in a tray will spawn an extra process (maybe even requiring network, like cddb lookups), which will delay some other process, which causes the error. Loading desktop pictures causes the same delay (but wouldn't need network, unless the picture is on a remote drive).