Was there a regression or is gtk-update-icon-cache now a hard dependency? I’m getting this in Ubuntu 16.04 (when using the PPA).

The following packages have unmet dependencies:
 gnome-gmail : Depends: gtk-update-icon-cache but it is not installable