This may be hard for some people who do not know how to use google properly so I will take one extra step and help the people who have problems with Wicd.
Code:
Add this to /etc/apt/sources.list:
deb http://www.backports.org/debian lenny-backports main contrib non-free
Follow this with apt-get update and then apt-get -t lenny-backports install wicd.