Comment 72 for bug 356152

root cause found!
workaround found!
It is a permission problem when you have installed from "alternate-CD"!

Checking /usr/share/doc/update-notifier/README gave me the deciding hint: "gksu is required". It is installed of course, but:

With alternate-CD you normally get a true root-account, which is one of the reasons why I have choosen that way (besides installing legacy-grub, a fixed network interface with fixed IP, ...).

"true root-account" does not include permissions for group "admin".
This is /etc/sudoers as from installation:

------------------------
Defaults env_reset

# Host alias specification

# User alias specification

# Cmnd alias specification

# User privilege specification
root ALL=(ALL) ALL

# Allow members of group sudo to execute any command after they have
# provided their password
# (Note that later entries override this, so you might need to move
# it further down)
%sudo ALL=(ALL) ALL
#
#includedir /etc/sudoers.d
-----------------------------

I now added permission for group "admin" and modified "Defaults:
---------------------
...
#Defaults env_reset
Defaults !lecture,tty_tickets,!fqdn,targetpw,timestamp_timeout = 0
....
# Members of the admin group may gain root privileges
%admin ALL=(ALL) ALL
-----------------------

and, to ask for root-password instead of the "admin-user" password for permission requests under GNOME I had to cheat polkit-1 by overriding the Ubuntu modifications in 51-ubuntu-admin.conf:

cp /etc/polkit-1/localauthority.conf.d/ 50-localauthority.conf /etc/polkit-1/localauthority.conf.d/52-ask-rootpw.conf

With theese modifications all works fine as expected.

At the end I do not know whom to blame for this nasty bug:
Ubuntu-installer on alternate-CD, polkit-1 configuration, update-manager for not accepting user to be in group "sudo", ...

Nevertheless it is a severe security issue for those who install fronm alternate-CD