kcheckpass does not need to have suid flag set (and it also does not have by default).
You probably have wrong ownership of /etc/shadow file - see bug 37407.
** Changed in: kdebase (Ubuntu)
Status: Unconfirmed => Needs Info
--
suid root flag of /usr/bin/kcheckpass reset
https://launchpad.net/bugs/49710