Então comecei a procurar uma solução, e a minha primeira hipótese foi o fato de o Xubuntu 16.04 ter um Kernel "antigo" (4.4.x). Então eu fiz o download do kernel 4.9.2 para amd64 de: http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.9.2/
Esse Kernel funcionou, algumas mensagens de erro na inicialização sumiram e, principalmente, conseguia ejetar o HD externo da porta USB 3.0 sem dar aquela trancada violenta. O problema é que vários programa não funcionam com o Kernel 4.9.2-040902, como o Virtualbox, então essa não é a solução ideal.
Então, tentei instalar o pacote linux-generic-hwe-16.04-edge para instalar o Kernel oficial do Ubuntu. Depois que instalei esse, praticamente tudo parou de funcionar: Wi-Fi, Ethernet, Monitor externo, portas USB, etc. Nem a versão 4.4.0-59, nem a 4.8.0-34 e nem 4.9.2-040902 faziam com que o sistema se recuperasse. E o pior é que não conseguia ejetar o HD externo de novo.
Fiquei com medo de que teria de formatar, mas então tomei atitudes:
1) Desinstalei os Kernels 4.8.0-34 e 4.9.2-040902;
2) Apaguei a configuração residual de tudo;
3) Reinstalei vários pacotes. Eu nunca uso apt-get clear, então eu os tinha salvos, permitindo-me reinstalar os pacotes sem internet:
Reinstalei o Kernel 4.9.2-040902, reiniciei, iniciei pelo Kernel 4.9.2-040902 e o sistema voltou a funcionar.
Venho através deste tópico apresentar minha indignação com o ocorrido, e também mostrar uma forma de salvar um sistema que parecia ser irrecuperável. O Kernel mais recente do repositório oficial que dá pra baixar com apt-get (4.8.0-34) quebrou o sistema, enquanto o baixado do site oficial mas instalado por fora (4.9.2-040902) funcionou melhor que o oficial suportado (4.4.0-59).