Si usas Ubuntu 12.04 o posteriores, deberías usar Synaptic con soporte para GTK3. No lo dudes. Mucho más rápido, mucho más limpio y mucho más integrado. Mejorará tu vida.
Abre ahora mismo un terminal y escribe:
sudo add-apt-repository ppa:webupd8team/unstable
sudo apt-get update
sudo apt-get install synaptic
Me lo agradecerás.
Fuente: ubuntuleon
