I think I have figured out why my machine has been playing up.
In both cases, my machine was trying to run kernel 3.19, but after checking Kernel.org, I found that this kernel version has been marked EOL.
I installed Fedora 21, which came with kernel 3.17 and worked, but after updating, it stopped working, with kernel 3.19. Forcing it to run on 3.17 was okay, though.
Good: Fedora, with Linux 3.17.4-301.fc21.x86_64
Bad: Fedora, with Linux 3.19.7-200.fc21.x86_64
Latest kernel release is 4.0.4, so I need to wait for Fedora to update.
Interestingly, it could also explain why I was also having trouble with Ubuntu, as it also ran 3.19. When trying to reinstall Ubuntu from the latest install image, it hung, presumably because it was trying to use the 3.19 Kernel. In theory, I could use an older installer (e.g. Utopic Unicorn) instead.
So now, I’m running Fedora with a 3.19 main kernel (which fails) and 3.17 secondary kernel. I was going to file a bug on Kernel.org, but found out about 3.19 being EOL, which means no bug fixes will be released, so there is no point in filing the bug.
On the plus side, my machine seems SO much more zippier running Fedora. Although trying to run Dota 2 seems a bit quirky. Dust: An Elysian Tail worked pretty well, as did Second Life (I was able to crank Singularity Viewer up to Ultra without major speed loss).
I still need to reinstall BOINC and any other missing apps I might have, and get used to using yum, yumex and dnf instead of apt-get, aptitude and synaptic all over again, but apart from that, it should be all good.