I had a funky Ubuntu upgrade some years ago. The first dist-upgrade didn't upgrade everything, and I was left in a kind-of between-version limbo. With nothing left to lose, I did an update/dist-upgrade cycle again and it sorted itself out. Only time it's ever happened to me.

And if you get really stuck apt-get -f install can also work miracles.

Wade.