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:
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