Experimente a versão flatpak dos mapas do gnome: link
Trabalhou para mim no Ubuntu 18.04 x64: os favoritos estão de volta e a função de pesquisa funciona como esperado.
1. Instalar o Flatpak
sudo add-apt-repository ppa:alexlarsson/flatpak
sudo apt update
sudo apt install flatpak
2. Instale o plugin do Software Flatpak
sudo apt install gnome-software-plugin-flatpak
3. Adicione o repositório Flathub
sudo flatpak remote-add --if-not-exists flathub https://flathub.org/repo/flathub.flatpakrepo
4. Reinicie (se necessário)
5. Instale o Gnome-Maps via Gnome-Software ou através da linha de comando
sudo flatpak install flathub org.gnome.Maps
6. Execute o aplicativo
flatpak run org.gnome.Maps