Using locate.updatedb doesn't work in Lion
Debugging pam can be tricky.

Have you tried making a real root shell with sudo -s and running the /usr/libexec/locate.updatedb command.

Alternatively, you could try making a new admin account to be sure your admin account has correct privelages/authentication. Any odd things like server or OpenLDAP that we should know of?