Buenas!
Bueno, para el tema de los gestores de paquetes cada uno tiene sus manías. A mi tambien me ha pasado eso que dices, no obstante, te pongo la forma de solucionarlo. No lo digo para que vayas a cambiar de gestor ni nada, pero lo pongo para que el problema no sea que te da este error.
sudo aptitude update && sudo aptitude safe-upgrade
con esto aptitude instala todos los paquetes a sus versiones mas recientes y solo borra paquetes que esten "unused". Se instalaran todos los paquetes que no esten instalados que vayan a resolver las dependencias.
Y si no se soluciona...
sudo aptitude update && sudo aptitude full-upgrade
Con esto aptitude actualiza los paquetes instalados a su version mas reciente instalando o eliminando si es necesario. Esta opcion es menos conservadora que la anterior y es mas fácil que se puedan ejecutar acciones no deseadas.
Muchas gracias por lo del ";" siempre se aprendre algo nuevo :D
Un saludo!
pulchras