Android devices stopped showing up in Nautilus (Ubuntu 18.04)

The solution is to reinstall Nautilus:

sudo apt-get remove nautilus
sudo apt-get install nautilus

I've found the results of the installation command especially interesting:

The following additional packages will be installed:
  gvfs-backends
(...)
Selecting previously unselected package gvfs-backends.
(...)
Setting up gvfs-backends (1.36.1-0ubuntu1) ...

It is possible I've removed gvfs-backends unwittingly while playing around with network and SMB.