Weird! Sounds like maybe `apt-get dist-upgrade` or `apt-get full-upgrade`. `upgrade` shouldn't uninstall anything or update your kernel as far as I know. `dist-upgrade` or `full-upgrade` could do either. If your `/boot` partition was exhausted or you lost power in the middle of a kernel upgrade, that could leave the system in a broken state.

At any rate, sorry you had such a frustrating experience.