my humble opinion is that mountain lion changed the way it handles the keyboard (I know because I am a VI user!) and my password has accented characters that are generated by double keyboard strike!
I created a new admin user and assigned to it the password èòàùç
sudo does not complain about the password.
The problem (for me at least) is TextExpander. God knows how many times I have "nuked & paved" my Air in order to get rid of this problem.
TextExpander has a setting that capitalises the first letter of the first word of a "sentence". You type your password correctly & TextExpander cleverly capitalises the first letter. You can turn this feature off on an app by app basis in the Preferences.
If you are not using TextExpander then have a look at what else you are running that does something similar i.e. autocorrect or something like this.
I have conatcted Smile & also had this problem echoed at https://discussions.apple.com/thread/4607694?start=0&tstart=0 by joshsmith01.
Hope this helps.
Thanks for the suggestion Mchw. I can't believe after all this time the solution has finally been discovered. It was exactly as you said, the problem was auto capitalisation in Text Expander. After quitting TE my sudo password worked, so I restarted TE then in TE preferences excluded Terminal.app from the auto capitalise function and everything is now as it should be. Thanks again for posting the solution.