I got sick of it, so I downloaded the install disc for 16.10, booted up the installation procedure and asked to repair the installation. That didn't work -- still problems. So I made a copy of my home directory on my second harddrive, started the installation procedure and instructed to wipe the existing install and re-install. There was a message that you'd lose everything -- but I didn't care, because I had made a copy of my homedir on the second harddisc, right?
Turns out that "wipe" also means "wipe every disc that's part of the installation, regardless of whether there are installation files on there or not". Which means my backup got wiped as well. It's intensely stupid, but that should teach me to make offline backups.
And I still have problems (though the video aspect seems to be solved, but I still get kernel updates that send the system in a reboot loop). I am seriously considering moving towards an Intel chip to get rid of these problems.