Tente tudo isso primeiro (como root, é claro):
# apt-get install -f
# dpkg --configure -a
# apt-get --fix-broken install
# apt-get --fix-missing install
Se isso não funcionar, tente instalar aptitude
.
# apt-get install aptitude
E corra
# aptitude update
# aptitude upgrade