En lugar de pasarle remove, tenés que pasarle purge. O sea, apt-get purge. Aunque yo te recomendaría que lo hicieras con aptitude. Está comprobado que resuelve mejor las dependencias. En resumen: aptitude purge paquete. O mejor aún, aptitude remove --purge paquete, de esta manera purgará el paquete junto con todos aquellos que van a quedar huérfanos.