¿Has probado a usar apt-get en vez de aptitude? A mi parecer, aptitude "le encanta el manejo de las dependencias" por lo que si te despistas te puede desinstalar gran cantidad de paquetes.
En cambio apt-get va directo al grano y desinstala el paquete que deseas y sus dependientes más próximos.
