Tente apt-get -f install para ver se ha alguma dependencia nao-resolvida.
debian:/home/deb# apt-get -f install Reading Package Lists... Done Building Dependency Tree... Done 0 packages upgraded, 0 newly installed, 0 to remove and 1 not upgraded. Creio não ser isto...
