I've known for a while that the proprietary NVidia drivers I downloaded some time back screwed with my system, unfortunately I hadn't realized just how bad until I tried upgrading from 8.04 to 8.10.

After the upgrade and reboot, X wouldn't start and my package manager complained about various libgl1-mesa packages. When I tried doing "apt-get -f install" as suggested, I would get the following error:

unable to create `./usr/lib/libGL.so.1.2': No such file or directory
among other things...

There's actually a pretty simple fix... I entered the following in a console:
dpkg-divert --remove /usr/lib/libGL.so.1.2
dpkg-divert --remove /usr/lib/libGL.so.1
apt-get -f install

All was well with the world - I still needed to manually reinstall my proprietary NVidia drivers, but at least now my package system wasn't broken anymore.