THIS HAS BEEN EDITED FOR THE CURRENT FILES AT https://pkgs.org/ FOR UBUNTU 16.04 PACKAGES WHICH SHOULD NOW INSTALL ANYWAY UNLESS YOU HAVE A PROBLEM AND NEED THE FILES BELOW!.
if you have just upgraded to Ubuntu (Mate) 16.04 and cannot install Google Earth, just follow the next few steps and you will be up and running.
When you download the GE package: https://www.google.com/earth/download/ge/agree.html
you will be told by Gdebi that certain dependencies aren't installed and the install will fail, go here: https://pkgs.org/
and search for the following 3 packages and install them:
all.deb package works for both 32 and 64 bit!:
lsb-invalid-mta (all.deb): https://pkgs.org/ubuntu-16.04/ubuntu-updates-universe-i386/lsb-invalid-mta_9.20160110ubuntu0.2_all.deb.html
lsb-security (64 Bit): https://pkgs.org/ubuntu-16.04/ubuntu-updates-universe-amd64/lsb-security_9.20160110ubuntu0.2_amd64.deb.html
32 bit: https://pkgs.org/ubuntu-16.04/ubuntu-updates-universe-i386/lsb-security_9.20160110ubuntu0.2_i386.deb.html
lsb-core (64 Bit): https://pkgs.org/ubuntu-16.04/ubuntu-updates-universe-amd64/lsb-core_9.20160110ubuntu0.2_amd64.deb.html
32 bit: https://pkgs.org/ubuntu-16.04/ubuntu-updates-universe-i386/lsb-core_9.20160110ubuntu0.2_i386.deb.html
then install Google Earth once those 3 packages have been installed.
If you get stuck at the very beginning, try using the following terminal command (Ctrl + Alt + t) and then install the following package directly from the Ubuntu repo:
sudo apt-get install lsb-core
Now try installing GE again, it should work!.