Наблюдал в Ubuntu 11.10.
При попытке поменять свой же (пользовательский) пароль командой passwd (а также при попытке поменять пароль юзера от рута) – выскакивало сообщение:
Ошибка при операциях с маркером проверки подлинности
и пароль не менялся.
Решение было найдено в инернете – нужно установить пакет libpam-cracklib и выполнить команду pam-auth-update (при запуске она выдала псевдо-меню с выбранными пунктами – я согласился с дефолтовыми вариантами и просто нажал Enter). Проблема решена.