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 chroot.
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.
