After some research it seems this is caused (weird, I know...) by the BIOS "Legacy Floppy" setting being enabled (it seems it's related to this). So to fix it, all I had to do is restart the computer and next to the "Floppy" setting in the BIOS I selected "Disabled" instead of "Legacy Floppy" - problem solved, as soon as Ubuntu booted, automount was working again and my USB devices were showing up in Nautilus again.
Hopefully this will help those of you having the same issue as I did.
Update: alternatively (thanks to Benplanet), run the following command in a terminal:
sudo modprobe -r floppy
And then restart your computer.