Originally Posted by ukiuki
You can NOT remove or purge with apt-get, it is only for install programs, dpkg is what you should use for that.
What distro are you running? Doh yes apt-get purge is what you would use.
There are several wicd packages, the ones that show up in Menu are:
wicd-gtk - wired and wireless network manager - GTK+ client
wicd-kde - Wired and wireless network manager - plasmoid
Although they should be removed when you remove 'wicd' which is just a metapackage.
Try running update-menus as user not root.
You can also do:
apt-get purge wicd*