Comment 2 for bug 665715

Thank you Fabio, this indeed solved the problem. I ran sudo apt-get clean and reinstalled the packages - since then I updated three times and authentication worked every time. Thanks again, bug report can be closed now.