Software Updater - Not all updates can be installed

The problem got solved after running sudo apt-get dist-upgrade.

What does this do?

From apt-get man page:

dist-upgrade in addition to performing the function of upgrade, also intelligently handles changing dependencies with new versions of packages; apt-get has a "smart" conflict resolution system, and it will attempt to upgrade the most important packages at the expense of less important ones if necessary. The dist-upgrade command may therefore remove some packages.

I was able to get past this issue, as per a post elsewhere on the net (forget where), by using Synaptic to upgrade my packages. Afterwards, the software updater was no longer complaining, and could fetch/install the updates since then.