As already said, the problem may be your PolicyKit configuration. I would be interested in the contents of the files in
/etc/polkit-1 directory and the file
/usr/share/polkit-1/actions/org.debian.apt.policy. The output can be lengthy, so you may want to compress it and upload it somewhere rather than copy it here...
grep -IR '^[^#]' /etc/polkit-1
EDIT: After you've uploaded the files I can see that the problem is in your
/var/lib/polkit-1/localauthority/50-local.d/20-xbmclive.pkla file which seems to have been installed by XBMC and effectively turns off all authentication via polkit (why it has done so and if it is really needed I don't know, I don't use this software).
[XBMC-Live user permissions]