I fixed the problem and the cause of it turned out to be very simple:
/boot was not mounted when I installed the proprietary drivers!
You see, I had an encrypted installation with
/boot residing on removable storage. Following the answer for this question (How to run scripts on start up?), I set up my system to run
umount /boot right before the login screen and I rebooted several times to make sure this was working reliably. Then I installed the AMD proprietary graphics drivers from here:
Following the installation and reboot of the system, I ended up with no display; the monitor was in power save mode which meant the most reliable way to diagnose this problem was using something known to be working: a live Ubuntu disc and
Having mounted all the partitions necessary, I
chroot into the installation and ran
apt-get remove on every package listed by
dpkg -l '*fglrx*'. From the output, I was able to spot that in the removal process, some files in
/boot were being modified and
update-initramfs was being run. Suspecting that the real problem might have been
/boot being inaccessible during the first installation of the proprietary drivers, I ran
apt-get install fglrx-updates fglrx-amdcccle-updates before rebooting the system.
And it worked!
Folks: make sure your
/boot partition is available before installing or removing any software/updates! You'll never know when
/boot might be needed.