After some tweaking on my ubuntu, wicd suddenly asks for the root password for every login. Turns out that this may be caused by the concurrency init settings: when wicd is started together with other scripts, it fails.

So I just go to /etc/rc?.d and renamed S??wicd so that it will be started alone. Problem gone.