I then remembered I had previously placed some new entries in the fstab, since I needed to mount some remote CIFS shares. Could this be the culprit?
Well, it seems it was exactly that: there is a bug in Network Manager which shuts down before unmounting the network shares. This will cause CIFS to hang and wait for 60 seconds or so for every share.
Even though the Ubuntu Wiki says that this bug has been solved since version 12.04, I have applied the suggested solution and it worked.
Now the shutdowns/reboots happen in an instant!
So, is the bug back? I don't know, but what I know is that this is how to fix this problem:
sudo ln -s /etc/init.d/umountnfs.sh /etc/rc0.d/K14umountnfs.sh
sudo ln -s /etc/init.d/umountnfs.sh /etc/rc6.d/K14umountnfs.sh
