Thanks to some people on the IRC channel, we were able to pinpoint the cause of the problem.
When installing firmware-amd-graphics, the initramfs is not rebuilt, which makes it impossible for the device to be used. Running `update-initramfs -u -k all` and rebooting fixed the problem. Regarding my other computer, it uses Intel graphics, so it must be an unrelated issue.
