apt-get w Debianie 4.0 nie ma funkcji autoremove. Po prostu funkcja ta występuje dopiero od wersji 0.7.x apt-get'a - Lenny ma 0.7.16, w Ubuntu od 8.04.
Przy okazji przypomnę, że od wydania "etch'a" jedynym rekomendowanym menadżerem pakietów pod konsolę (interfejs graficzny jest w powijakach) jest aptitude KROPKA! :-P