In an effort to consolidate the great troubleshooting solutions offered in this thread, we have summarized the information contained here into a TechNet Wiki article at the following location:

 

How to change the local Administrator password on domain member computers (dsforum2wiki)

Please feel free to provide feedback on the article at the Wiki site, or you can edit the article itself.

 

Update: A new solution for managing local Administrator passwords is now available on MSDN at http://code.msdn.microsoft.com/Solution-for-management-of-ae44e789. This solution is a client side GPO extension (CSE) that is simple and scalable, amongst many other benefits.
 

Justin Hall [MSFT]

Active Directory Documentation Team