Today at work I have a wired connection instead of Wifi and with auto-login enabled again, plasma started but then I could not launch any programs. I wonder whether it is indeed a timing problem (as fvogt indicated on IRC) during startup which results in a newly set hostname. And indeed, I have different hostnames depending on the network I am in.