Today I upgraded my Ubuntu Gnome 15.10 to 16.04 Xenial Xerus. I was surprised to find in the details that it removes gdm. I started the update and it went normal until it said ubuntu-gnome-desktop was broken due to unresolved dependencies. The GUI upgrade process that I had used closed and I was left with a system upgraded by half. But it was still running, so I started a terminal and started aptitude. It suggested to install various packages to resolve dependencies, especially gdm3, gnome-shell, gnome-shell-extensions and gnome-session. It also proposed to remove unused packages, which were not removed as the upgrade process had stopped half way. I followed aptitudes suggestions, but it left two packages not upgraded: adwaita-icon-theme and gnome-session.

And this took me quite a while to solve. There are two packages: adwaita-icon-theme and adwaita-icon-theme-full. The first one contains a subset of icons, whereas the second one contains all icons. The ubuntu-gnome-desktop requires the adwaita-icon-theme-full package, which in turn requires the adwaita-icon-theme package. The adwaita-icon-theme had an upgrade from version 3.18.0-2ubuntu3 to 3.18.0-2ubuntu3.1. The adwaita-icon-theme-full package requires that it is exactly the same version as adwaita-icon-theme, but the only version that apt found was 3.18.0-2ubuntu3.

Then I found out that adwaita-icon-theme-full is in the universe repository, whereas adwaita-icon-theme is in main. In my sources.list, I had the following:

deb http://de.archive.ubuntu.com/ubuntu/ xenial-proposed main restricted
deb http://de.archive.ubuntu.com/ubuntu/ xenial-proposed main restricted

Therefore, the new version of adwaita-icon-theme was found in the main repository. But universe (and multiverse) repositories were missing  the proposed level, and this was the reason why the new version of adwaita-icon-theme-full was not found by apt. So the solution was simple: Just changing the above lines in sources.list like this, adding universe and multiverse repositories:

deb http://de.archive.ubuntu.com/ubuntu/ xenial-proposed main restricted universe multiverse
deb http://de.archive.ubuntu.com/ubuntu/ xenial-proposed main restricted universe multiverse

Then it updated the remaining packages normally using:

aptitude update
aptitude safe-upgrade

So lesson learned is:
If you add the proposed level in your sources.list, make sure you add it for all repositories you use, e.g. including universe and multiverse, not only main.

Hope this helps somebody who runs into the same issue.