Si te has habituado al aptitude (un gestor de instalacion usado en debian y ubuntu y derivaras) pero te has instalado ubuntu 10.10 (la ultima version publicada de canonical) hay una manera de solucionar este pequeño inconveniente de la siguiente:
En Ubuntu/Xubuntu vaya a aplicaciones -> accesorios -> terminal
En Kubuntu vaya a K y ponga konsole y ejecutelo.
Para instalarlo basicamente hay que instalarlo (sudo apt-get install aptitude -y)
Despues de instalarlo podra ejecutarlo sin problemas.
Fuente original (aunque lo escriba yo lo encontre aqui).