Just had a very similar problem and wanted to post the cause solution in case anyone else runs into it.

In my case, I was mucking around trying to get PHP/Apache running, but the version of /usr/lib/libxml2.dylib I had was out of date. So I downloaded a new one and installed that (but it was installed to /usr/local/lib). So without thinking I mv'ed the one in /usr/lib to a backup dir, thinking I'd move the one from local lib in there next. But I got sidetracked and forgot, as PHP/Apache was working fine with it in /usr/local/lib.

Well, I guess sudo relies on that lib, as sudo was broken the next time I tried (always rejected my password as described above). After seeing Spotlight and Installer crashes, I realized what happened.

I had to go into single user mode to move the original one back (haven't tried putting the new one in /usr/lib yet).

So, anyways, I can't say how to diagnose a problem like mine, but can say if you changed anything in /usr/lib, you may see the symptoms listed in this thread.

I wasn't able to authenticate as root in terminal but I could in any other system dialog (ex. lock icon in System Preferences). I found an easy solution that worked for me. I just changed the root password in terminal (sudo passwd root). The strange thing is my admin password worked fine to change the root password. From then on I had no issue. Hope this helps someone.